Graph types¶

Class	Type	Self-loops allowed	Parallel edges allowed
Graph	undirected	Yes	No
DiGraph	directed	Yes	No

Graph¶

Undirected graphs with self loops

class graphscope.experimental.nx.Graph(incoming_graph_data=None, **attr)[source]¶

Base class for undirected graphs.

A Graph stores nodes and edges with optional data, or attributes.

Graphs hold undirected edges. Self loops are allowed but multiple (parallel) edges are not.

Nodes can be strings or integers objects with optional key/value attributes.

Edges are represented as links between nodes with optional key/value attributes

Parameters

incoming_graph_data (input graph (optional, default: None)) – Data to initialize graph. If None (default) an empty graph is created. The data can be any format that is supported by the to_nx_graph() function, currently including edge list, dict of dicts, dict of lists, NetworkX graph, NumPy matrix or 2d ndarray, SciPy sparse matrix, or a graphscope graph.
attr (keyword arguments, optional (default= no attributes)) – Attributes to add to graph as key=value pairs.

See also

DiGraph, graphscope.Graph

Examples

Create an empty graph structure (a “null graph”) with no nodes and no edges.

>>> G = nx.Graph()

G can be grown in several ways.

Nodes:

Add one node at a time:

>>> G.add_node(1)

Add the nodes from any container (a list, dict, set or even the lines from a file or the nodes from another graph).

>>> G.add_nodes_from([2, 3])
>>> G.add_nodes_from(range(100, 110))
>>> H = nx.path_graph(10)
>>> G.add_nodes_from(H)

In addition integers, strings can represent a node.

>>> G.add_node('a node')

Edges:

G can also be grown by adding edges.

Add one edge,

>>> G.add_edge(1, 2)

a list of edges,

>>> G.add_edges_from([(1, 2), (1, 3)])

or a collection of edges,

>>> G.add_edges_from(H.edges)

If some edges connect nodes not yet in the graph, the nodes are added automatically. There are no errors when adding nodes or edges that already exist.

Attributes:

Each graph, node, and edge can hold key/value attribute pairs in an associated attribute dictionary (the keys must be string). By default these are empty, but can be added or changed using add_edge, add_node or direct manipulation of the attribute dictionaries named graph, node and edge respectively.

>>> G = nx.Graph(day="Friday")
>>> G.graph
{'day': 'Friday'}

Add node attributes using add_node(), add_nodes_from() or G.nodes

>>> G.add_node(1, time='5pm')
>>> G.add_nodes_from([3], time='2pm')
>>> G.nodes[1]
{'time': '5pm'}
>>> G.nodes[1]['room'] = 714  # node must exist already to use G.nodes
>>> del G.nodes[1]['room']  # remove attribute
>>> list(G.nodes(data=True))
[(1, {'time': '5pm'}), (3, {'time': '2pm'})]

Add edge attributes using add_edge(), add_edges_from(), subscript notation, or G.edges.

>>> G.add_edge(1, 2, weight=4.7 )
>>> G.add_edges_from([(3, 4), (4, 5)], color='red')
>>> G.add_edges_from([(1, 2, {'color': 'blue'}), (2, 3, {'weight': 8})])
>>> G[1][2]['weight'] = 4.7
>>> G.edges[1, 2]['weight'] = 4

Warning: we protect the graph data structure by making G.edges a read-only dict-like structure. However, you can assign to attributes in e.g. G.edges[1, 2]. Thus, use 2 sets of brackets to add/change data attributes: G.edges[1, 2][‘weight’] = 4

Shortcuts:

Many common graph features allow python syntax to speed reporting.

>>> 1 in G     # check if node in graph
True
>>> [n for n in G if n < 3]  # iterate through nodes
[1, 2]
>>> len(G)  # number of nodes in graph
5

Often the best way to traverse all edges of a graph is via the neighbors. The neighbors are reported as an adjacency-dict G.adj or G.adjacency()

>>> for n, nbrsdict in G.adjacency():
...     for nbr, eattr in nbrsdict.items():
...        if 'weight' in eattr:
...            # Do something useful with the edges
...            pass

But the edges() method is often more convenient:

>>> for u, v, weight in G.edges.data('weight'):
...     if weight is not None:
...         # Do something useful with the edges
...         pass

Reporting:

Simple graph information is obtained using object-attributes and methods. Reporting typically provides views instead of containers to reduce memory usage. The views update as the graph is updated similarly to dict-views. The objects nodes, `edges and adj provide access to data attributes via lookup (e.g. nodes[n], `edges[u, v], adj[u][v]) and iteration (e.g. nodes.items(), nodes.data(‘color’), nodes.data(‘color’, default=’blue’) and similarly for edges) Views exist for nodes, edges, neighbors()/adj and degree.

For details on these and other miscellaneous methods, see below.

Adding and removing nodes and edges

`Graph.__init__`([incoming_graph_data])	Initialize a graph with edges, name, or graph attributes
`Graph.add_node`(node_for_adding, **attr)	Add a single node node_for_adding and update node attributes.
`Graph.add_nodes_from`(nodes_for_adding, **attr)	Add multiple nodes.
`Graph.remove_node`(n)	Remove node n.
`Graph.remove_nodes_from`(nodes_for_removing)	Remove multiple nodes.
`Graph.add_edge`(u_of_edge, v_of_edge, **attr)	Add an edge between u and v.
`Graph.add_edges_from`(ebunch_to_add, **attr)	Add all the edges in ebunch_to_add
`Graph.add_weighted_edges_from`(ebunch_to_add)	Add weighted edges in ebunch_to_add with specified weight attr
`Graph.remove_edge`(u, v)	Remove the edge between u and v.
`Graph.remove_edges_from`(ebunch)	Remove all edges specified in ebunch.
`Graph.update`([edges, nodes])	Update the graph using nodes/edges/graphs as input.
`Graph.clear`()	Remove all nodes and edges from the graph.

Reporting nodes edges and neighbors

`Graph.nodes`	A NodeView of the Graph as G.nodes or G.nodes().
`Graph.__iter__`()	Iterate over the nodes.
`Graph.has_node`(n)	Returns True if the graph contains the node n.
`Graph.get_node_data`(**kwargs)
`Graph.__contains__`(n)	Returns True if n is a node, False otherwise.
`Graph.edges`	An EdgesView of the Graph as G.edges or G.edges().
`Graph.has_edge`(u, v)	Returns True if the edge (u, v) is in the graph.
`Graph.get_edge_data`(u, v[, default])	Returns the attribute dictionary associated with edge (u, v).
`Graph.neighbors`(n)	Returns an iterator over all neighbors of node n.
`Graph.adj`	Graph adjacency object holding the neighbors of each node.
`Graph.__getitem__`(n)	Return a dict of neighbors of node n.
`Graph.adjacency`()	Returns an iterator over (node, adjacency dict) tuples for all nodes.
`Graph.nbunch_iter`([nbunch])	Returns an iterator over nodes contained in nbunch that are also in the graph.

Counting nodes edges and neighbors

`Graph.order`()	Returns the number of nodes in the graph.
`Graph.number_of_nodes`()	Returns the number of nodes in the graph.
`Graph.__len__`()	Returns the number of nodes in the graph.
`Graph.degree`	A DegreeView for the Graph as G.degree or G.degree().
`Graph.size`([weight])	Returns the number of edges or total of all edge weights.
`Graph.number_of_edges`([u, v])	Returns the number of edges between two nodes.

Making copies and subgraphs

`Graph.copy`([as_view])	Returns a copy of the graph.
`Graph.to_undirected`([as_view])	Returns an undirected copy of the graph.
`Graph.to_directed`([as_view])	Returns a directed representation of the graph.
`Graph.subgraph`(nodes)	Returns a SubGraph view of the subgraph induced on nodes.
`Graph.edge_subgraph`(edges)	Returns the subgraph induced by the specified edges.

Project simple graph

Graph.project_to_simple([v_prop, e_prop])

Project nx graph to a simple graph to run builtin alogorithms.

DiGraph¶

Directed graphs with self loops

class graphscope.experimental.nx.DiGraph(incoming_graph_data=None, **attr)[source]¶

Base class for directed graphs.

A DiGraph stores nodes and edges with optional data, or attributes.

DiGraphs hold directed edges. Self loops are allowed but multiple (parallel) edges are not.

Nodes can be strings or integers objects with optional key/value attributes.

Edges are represented as links between nodes with optional key/value attributes.

Parameters

incoming_graph_data (input graph (optional, default: None)) – Data to initialize graph. If None (default) an empty graph is created. The data can be any format that is supported by the to_networkx_graph() function, currently including edge list, dict of dicts, dict of lists, NetworkX graph, NumPy matrix or 2d ndarray, SciPy sparse matrix, or a graphscope graph.
attr (keyword arguments, optional (default= no attributes)) – Attributes to add to graph as key=value pairs.

See also

Graph, graphscope.Graph

Examples

Create an empty graph structure (a “null graph”) with no nodes and no edges.

>>> G = nx.DiGraph()

G can be grown in several ways.

Nodes:

Add one node at a time:

>>> G.add_node(1)

Add the nodes from any container (a list, dict, set or even the lines from a file or the nodes from another graph).

>>> G.add_nodes_from([2, 3])
>>> G.add_nodes_from(range(100, 110))
>>> H = nx.path_graph(10)
>>> G.add_nodes_from(H)

In addition integers, strings can represent a node.

>>> G.add_node('a node')

Edges:

G can also be grown by adding edges.

Add one edge,

>>> G.add_edge(1, 2)

a list of edges,

>>> G.add_edges_from([(1, 2), (1, 3)])

or a collection of edges,

>>> G.add_edges_from(H.edges)

If some edges connect nodes not yet in the graph, the nodes are added automatically. There are no errors when adding nodes or edges that already exist.

Attributes:

Each graph, node, and edge can hold key/value attribute pairs in an associated attribute dictionary (the keys must be hashable). By default these are empty, but can be added or changed using add_edge, add_node or direct manipulation of the attribute dictionaries named graph, node and edge respectively.

>>> G = nx.DiGraph(day="Friday")
>>> G.graph
{'day': 'Friday'}

Add node attributes using add_node(), add_nodes_from() or G.nodes

>>> G.add_node(1, time='5pm')
>>> G.add_nodes_from([3], time='2pm')
>>> G.nodes[1]
{'time': '5pm'}
>>> G.nodes[1]['room'] = 714
>>> del G.nodes[1]['room'] # remove attribute
>>> list(G.nodes(data=True))
[(1, {'time': '5pm'}), (3, {'time': '2pm'})]

Add edge attributes using add_edge(), add_edges_from(), subscript notation, or G.edges.

>>> G.add_edge(1, 2, weight=4.7 )
>>> G.add_edges_from([(3, 4), (4, 5)], color='red')
>>> G.add_edges_from([(1, 2, {'color':'blue'}), (2, 3, {'weight':8})])
>>> G[1][2]['weight'] = 4.7
>>> G.edges[1, 2]['weight'] = 4

Warning: we protect the graph data structure by making G.edges[1, 2] a read-only dict-like structure. However, you can assign to attributes in e.g. G.edges[1, 2]. Thus, use 2 sets of brackets to add/change data attributes: G.edges[1, 2][‘weight’] = 4 (For multigraphs: MG.edges[u, v, key][name] = value).

Shortcuts:

Many common graph features allow python syntax to speed reporting.

>>> 1 in G     # check if node in graph
True
>>> [n for n in G if n < 3]  # iterate through nodes
[1, 2]
>>> len(G)  # number of nodes in graph
5

Often the best way to traverse all edges of a graph is via the neighbors. The neighbors are reported as an adjacency-dict G.adj or G.adjacency()

>>> for n, nbrsdict in G.adjacency():
...     for nbr, eattr in nbrsdict.items():
...        if 'weight' in eattr:
...            # Do something useful with the edges
...            pass

But the edges reporting object is often more convenient:

>>> for u, v, weight in G.edges(data='weight'):
...     if weight is not None:
...         # Do something useful with the edges
...         pass

Reporting:

Simple graph information is obtained using object-attributes and methods. Reporting usually provides views instead of containers to reduce memory usage. The views update as the graph is updated similarly to dict-views. The objects nodes, `edges and adj provide access to data attributes via lookup (e.g. nodes[n], `edges[u, v], adj[u][v]) and iteration (e.g. nodes.items(), nodes.data(‘color’), nodes.data(‘color’, default=’blue’) and similarly for edges) Views exist for nodes, edges, neighbors()/adj and degree.

For details on these and other miscellaneous methods, see below.

Adding and removing nodes and edges

`DiGraph.__init__`([incoming_graph_data])	Initialize a graph with edges, name, or graph attributes
`DiGraph.add_node`(node_for_adding, **attr)	Add a single node node_for_adding and update node attributes.
`DiGraph.add_nodes_from`(nodes_for_adding, **attr)	Add multiple nodes.
`DiGraph.remove_node`(n)	Remove node n.
`DiGraph.remove_nodes_from`(nodes_for_removing)	Remove multiple nodes.
`DiGraph.add_edge`(u_of_edge, v_of_edge, **attr)	Add an edge between u and v.
`DiGraph.add_edges_from`(ebunch_to_add, **attr)	Add all the edges in ebunch_to_add
`DiGraph.add_weighted_edges_from`(ebunch_to_add)	Add weighted edges in ebunch_to_add with specified weight attr
`DiGraph.remove_edge`(u, v)	Remove the edge between u and v.
`DiGraph.remove_edges_from`(ebunch)	Remove all edges specified in ebunch.
`DiGraph.update`([edges, nodes])	Update the graph using nodes/edges/graphs as input.
`DiGraph.clear`()	Remove all nodes and edges from the graph.

Reporting nodes edges and neighbors

`DiGraph.nodes`	A NodeView of the Graph as G.nodes or G.nodes().
`DiGraph.__iter__`()	Iterate over the nodes.
`DiGraph.has_node`(n)	Returns True if the graph contains the node n.
`DiGraph.__contains__`(n)	Returns True if n is a node, False otherwise.
`DiGraph.edges`	An OutEdgeView of the DiGraph as G.edges or G.edges().
`DiGraph.out_edges`	An OutEdgeView of the DiGraph as G.edges or G.edges().
`DiGraph.in_edges`	An InEdgeView of the Graph as G.in_edges or G.in_edges().
`DiGraph.has_edge`(u, v)	Returns True if the edge (u, v) is in the graph.
`DiGraph.get_edge_data`(u, v[, default])	Returns the attribute dictionary associated with edge (u, v).
`DiGraph.neighbors`(n)	Returns an iterator over successor nodes of n.
`DiGraph.adj`	Graph adjacency object holding the successors of each node.
`DiGraph.__getitem__`(n)	Return a dict of neighbors of node n.
`DiGraph.successors`(n)	Returns an iterator over successor nodes of n.
`DiGraph.succ`	Graph adjacency object holding the successors of each node.
`DiGraph.predecessors`(n)	Returns an iterator over predecessor nodes of n.
`DiGraph.pred`	Graph adjacency object holding the predecessors of each node.
`DiGraph.adjacency`()	Returns an iterator over (node, adjacency dict) tuples for all nodes.
`DiGraph.nbunch_iter`([nbunch])	Returns an iterator over nodes contained in nbunch that are also in the graph.

Counting nodes edges and neighbors

`DiGraph.order`()	Returns the number of nodes in the graph.
`DiGraph.number_of_nodes`()	Returns the number of nodes in the graph.
`DiGraph.__len__`()	Returns the number of nodes in the graph.
`DiGraph.degree`	A DegreeView for the Graph as G.degree or G.degree().
`DiGraph.in_degree`	An InDegreeView for (node, in_degree) or in_degree for single node.
`DiGraph.out_degree`	An OutDegreeView for (node, out_degree)
`DiGraph.size`([weight])	Returns the number of edges or total of all edge weights.
`DiGraph.number_of_edges`([u, v])	Returns the number of edges between two nodes.

Making copies and subgraphs

`DiGraph.copy`([as_view])	Returns a copy of the graph.
`DiGraph.to_undirected`([as_view])	Returns an undirected copy of the graph.
`DiGraph.to_directed`([as_view])	Returns a directed representation of the graph.
`DiGraph.subgraph`(nodes)	Returns a SubGraph view of the subgraph induced on nodes.
`DiGraph.edge_subgraph`(edges)	Returns the subgraph induced by the specified edges.
`DiGraph.reverse`([copy])	Returns the reverse of the graph.

Project simple graph

DiGraph.project_to_simple([v_prop, e_prop])

Project nx graph to a simple graph to run builtin alogorithms.

Reading graphs¶

Edge List¶

graphscope.experimental.nx.read_edgelist(path, comments='#', delimiter=None, create_using=None, nodetype=None, data=True, edgetype=None, encoding='utf-8')[source]¶

Read a graph from a list of edges.

Parameters

path (file or string) – File or filename to read. If a file is provided, it must be opened in ‘rb’ mode. Filenames ending in .gz or .bz2 will be uncompressed.
comments (string, optional) – The character used to indicate the start of a comment.
delimiter (string, optional) – The string used to separate values. The default is whitespace.
create_using (NetworkX graph constructor, optional (default=nx.Graph)) – Graph type to create. If graph instance, then cleared before populated.
nodetype (int, float, str, Python type, optional) – Convert node data from strings to specified type
data (bool or list of (label,type) tuples) – Tuples specifying dictionary key names and types for edge data
edgetype (int, float, str, Python type, optional OBSOLETE) – Convert edge data from strings to specified type and use as ‘weight’
encoding (string, optional) – Specify which encoding to use when reading file.

Returns

G – A networkx Graph or other type specified with create_using

Return type

graph

Examples

>>> nx.write_edgelist(nx.path_graph(4), "test.edgelist")
>>> G = nx.read_edgelist("test.edgelist")

>>> fh = open("test.edgelist", "rb")
>>> G = nx.read_edgelist(fh)
>>> fh.close()

>>> G = nx.read_edgelist("test.edgelist", nodetype=int)
>>> G = nx.read_edgelist("test.edgelist", create_using=nx.DiGraph)

Edgelist with data in a list:

>>> textline = "1 2 3"
>>> fh = open("test.edgelist", "w")
>>> d = fh.write(textline)
>>> fh.close()
>>> G = nx.read_edgelist("test.edgelist", nodetype=int, data=(("weight", float),))
>>> list(G)
[1, 2]
>>> list(G.edges(data=True))
[(1, 2, {'weight': 3.0})]

See parse_edgelist() for more examples of formatting.

See also

parse_edgelist, write_edgelist

Notes

Since nodes must be hashable, the function nodetype must return hashable types (e.g. int, float, str, frozenset - or tuples of those, etc.)

Adjacency List¶

graphscope.experimental.nx.read_adjlist(path, comments='#', delimiter=None, create_using=None, nodetype=None, encoding='utf-8')[source]¶

Read graph in adjacency list format from path.

Parameters

path (string or file) – Filename or file handle to read. Filenames ending in .gz or .bz2 will be uncompressed.
create_using (NetworkX graph constructor, optional (default=nx.Graph)) – Graph type to create. If graph instance, then cleared before populated.
nodetype (Python type, optional) – Convert nodes to this type.
comments (string, optional) – Marker for comment lines
delimiter (string, optional) – Separator for node labels. The default is whitespace.

Returns

G – The graph corresponding to the lines in adjacency list format.

Return type

NetworkX graph

Examples

>>> G = nx.path_graph(4)
>>> nx.write_adjlist(G, "test.adjlist")
>>> G = nx.read_adjlist("test.adjlist")

The path can be a filehandle or a string with the name of the file. If a filehandle is provided, it has to be opened in ‘rb’ mode.

>>> fh = open("test.adjlist", "rb")
>>> G = nx.read_adjlist(fh)

Filenames ending in .gz or .bz2 will be compressed.

>>> nx.write_adjlist(G, "test.adjlist.gz")
>>> G = nx.read_adjlist("test.adjlist.gz")

The optional nodetype is a function to convert node strings to nodetype.

For example

>>> G = nx.read_adjlist("test.adjlist", nodetype=int)

will attempt to convert all nodes to integer type.

Since nodes must be hashable, the function nodetype must return hashable types (e.g. int, float, str, frozenset - or tuples of those, etc.)

The optional create_using parameter indicates the type of NetworkX graph created. The default is nx.Graph, an undirected graph. To read the data as a directed graph use

>>> G = nx.read_adjlist("test.adjlist", create_using=nx.DiGraph)

Notes

This format does not store graph or node data.

See also

write_adjlist

Algorithms on mutable graphs¶

graphscope.experimental.nx.Graph.project_to_simple(self, v_prop=None, e_prop=None)¶

Project nx graph to a simple graph to run builtin alogorithms.

A simple graph is a accesser wrapper of property graph that only single edge attribute and single node attribute are available.

Parameters

v_prop (the node attribute key to project, (optional, default None)) –
e_prop (the edge attribute key to project, (optional, default None)) –

Returns

simple_graph – A nx.Graph object that hold a simple graph projected by host property graph.

Return type

nx.Graph or nx.DiGraph

Notes

the method is implicit called in builtin apps.

graphscope.experimental.nx.builtin.pagerank(G, alpha=0.85, max_iter=100, tol=1e-06)¶

Returns the PageRank of the nodes in the graph.

PageRank computes a ranking of the nodes in the graph G based on the structure of the incoming links. It was originally designed as an algorithm to rank web pages.

Parameters

G (graph) – A NetworkX graph. Undirected graphs will be converted to a directed graph with two directed edges for each undirected edge.
alpha (float, optional) – Damping parameter for PageRank, default=0.85.
personalization (dict, optional) – The “personalization vector” consisting of a dictionary with a key some subset of graph nodes and personalization value each of those. At least one personalization value must be non-zero. If not specfiied, a nodes personalization value will be zero. By default, a uniform distribution is used.
max_iter (integer, optional) – Maximum number of iterations in power method eigenvalue solver.
tol (float, optional) – Error tolerance used to check convergence in power method solver.
nstart (dictionary, optional) – Starting value of PageRank iteration for each node.
weight (key, optional) – Edge data key to use as weight. If None weights are set to 1.
dangling (dict, optional) – The outedges to be assigned to any “dangling” nodes, i.e., nodes without any outedges. The dict key is the node the outedge points to and the dict value is the weight of that outedge. By default, dangling nodes are given outedges according to the personalization vector (uniform if not specified). This must be selected to result in an irreducible transition matrix (see notes under google_matrix). It may be common to have the dangling dict to be the same as the personalization dict.

Returns

pagerank – Dictionary of nodes with PageRank as value

Return type

dictionary

Examples

>>> G = nx.DiGraph(nx.path_graph(4))
>>> pr = nx.pagerank(G, alpha=0.9)

Notes

The eigenvector calculation is done by the power iteration method and has no guarantee of convergence. The iteration will stop after an error tolerance of len(G) * tol has been reached. If the number of iterations exceed max_iter, a networkx.exception.PowerIterationFailedConvergence exception is raised.

The PageRank algorithm was designed for directed graphs but this algorithm does not check if the input graph is directed and will execute on undirected graphs by converting each edge in the directed graph to two edges.

See also

pagerank_numpy, pagerank_scipy, google_matrix

Raises: PowerIterationFailedConvergence – If the algorithm fails to converge to the specified tolerance within the specified number of iterations of the power iteration method.

References

1: A. Langville and C. Meyer, “A survey of eigenvector methods of web information retrieval.” http://citeseer.ist.psu.edu/713792.html
2: Page, Lawrence; Brin, Sergey; Motwani, Rajeev and Winograd, Terry, The PageRank citation ranking: Bringing order to the Web. 1999 http://dbpubs.stanford.edu:8090/pub/showDoc.Fulltext?lang=en&doc=1999-66&format=pdf

graphscope.experimental.nx.builtin.hits(G, max_iter=100, tol=1e-08, normalized=True)¶

Returns HITS hubs and authorities values for nodes.

The HITS algorithm computes two numbers for a node. Authorities estimates the node value based on the incoming links. Hubs estimates the node value based on outgoing links.

Parameters

G (graph) – A NetworkX graph
max_iter (integer, optional) – Maximum number of iterations in power method.
tol (float, optional) – Error tolerance used to check convergence in power method iteration.
nstart (dictionary, optional) – Starting value of each node for power method iteration.
normalized (bool (default=True)) – Normalize results by the sum of all of the values.

Returns

(hubs,authorities) – Two dictionaries keyed by node containing the hub and authority values.

Return type

two-tuple of dictionaries

Raises

PowerIterationFailedConvergence – If the algorithm fails to converge to the specified tolerance within the specified number of iterations of the power iteration method.

Examples

>>> G = nx.path_graph(4)
>>> h, a = nx.hits(G)

Notes

The eigenvector calculation is done by the power iteration method and has no guarantee of convergence. The iteration will stop after max_iter iterations or an error tolerance of number_of_nodes(G)*tol has been reached.

The HITS algorithm was designed for directed graphs but this algorithm does not check if the input graph is directed and will execute on undirected graphs.

References

1: A. Langville and C. Meyer, “A survey of eigenvector methods of web information retrieval.” http://citeseer.ist.psu.edu/713792.html
2: Jon Kleinberg, Authoritative sources in a hyperlinked environment Journal of the ACM 46 (5): 604-32, 1999. doi:10.1145/324133.324140. http://www.cs.cornell.edu/home/kleinber/auth.pdf.

graphscope.experimental.nx.builtin.degree_centrality(G)¶

Compute the degree centrality for nodes.

The degree centrality for a node v is the fraction of nodes it is connected to.

Parameters: G (graph) – A networkx graph
Returns: nodes – Dictionary of nodes with degree centrality as the value.
Return type: dictionary

See also

betweenness_centrality, load_centrality, eigenvector_centrality

Notes

The degree centrality values are normalized by dividing by the maximum possible degree in a simple graph n-1 where n is the number of nodes in G.

For multigraphs or graphs with self loops the maximum degree might be higher than n-1 and values of degree centrality greater than 1 are possible.

graphscope.experimental.nx.builtin.in_degree_centrality(G)¶

Compute the in-degree centrality for nodes.

The in-degree centrality for a node v is the fraction of nodes its incoming edges are connected to.

Parameters: G (graph) – A NetworkX graph
Returns: nodes – Dictionary of nodes with in-degree centrality as values.
Return type: dictionary
Raises: NetworkXNotImplemented – If G is undirected.

Notes

The degree centrality values are normalized by dividing by the maximum possible degree in a simple graph n-1 where n is the number of nodes in G.

For multigraphs or graphs with self loops the maximum degree might be higher than n-1 and values of degree centrality greater than 1 are possible.

graphscope.experimental.nx.builtin.out_degree_centrality(G)¶

Compute the out-degree centrality for nodes.

The out-degree centrality for a node v is the fraction of nodes its outgoing edges are connected to.

Parameters: G (graph) – A NetworkX graph
Returns: nodes – Dictionary of nodes with out-degree centrality as values.
Return type: dictionary
Raises: NetworkXNotImplemented – If G is undirected.

Notes

The degree centrality values are normalized by dividing by the maximum possible degree in a simple graph n-1 where n is the number of nodes in G.

For multigraphs or graphs with self loops the maximum degree might be higher than n-1 and values of degree centrality greater than 1 are possible.

graphscope.experimental.nx.builtin.eigenvector_centrality(G, max_iter=100, tol=1e-06, weight=None)¶

Compute the eigenvector centrality for the graph G.

Eigenvector centrality computes the centrality for a node based on the centrality of its neighbors. The eigenvector centrality for node $i$ is the $i$-th element of the vector $x$ defined by the equation

\[Ax = \lambda x\]

where $A$ is the adjacency matrix of the graph G with eigenvalue $lambda$. By virtue of the Perron–Frobenius theorem, there is a unique solution $x$, all of whose entries are positive, if $lambda$ is the largest eigenvalue of the adjacency matrix $A$ ([2]_).

Parameters

G (graph) – A networkx graph
max_iter (integer, optional (default=100)) – Maximum number of iterations in power method.
tol (float, optional (default=1.0e-6)) – Error tolerance used to check convergence in power method iteration.
nstart (dictionary, optional (default=None)) – Starting value of eigenvector iteration for each node.
weight (None or string, optional (default=None)) – If None, all edge weights are considered equal. Otherwise holds the name of the edge attribute used as weight.

Returns

nodes – Dictionary of nodes with eigenvector centrality as the value.

Return type

dictionary

Examples

>>> G = nx.path_graph(4)
>>> centrality = nx.eigenvector_centrality(G)
>>> sorted((v, f"{c:0.2f}") for v, c in centrality.items())
[(0, '0.37'), (1, '0.60'), (2, '0.60'), (3, '0.37')]

Raises

NetworkXPointlessConcept – If the graph G is the null graph.
NetworkXError – If each value in nstart is zero.
PowerIterationFailedConvergence – If the algorithm fails to converge to the specified tolerance within the specified number of iterations of the power iteration method.

See also

eigenvector_centrality_numpy, pagerank, hits

Notes

The measure was introduced by [1]_ and is discussed in [2]_.

The power iteration method is used to compute the eigenvector and convergence is not guaranteed. Our method stops after max_iter iterations or when the change in the computed vector between two iterations is smaller than an error tolerance of G.number_of_nodes() * tol. This implementation uses ($A + I$) rather than the adjacency matrix $A$ because it shifts the spectrum to enable discerning the correct eigenvector even for networks with multiple dominant eigenvalues.

For directed graphs this is “left” eigenvector centrality which corresponds to the in-edges in the graph. For out-edges eigenvector centrality first reverse the graph with G.reverse().

References

1: Phillip Bonacich. “Power and Centrality: A Family of Measures.” American Journal of Sociology 92(5):1170–1182, 1986 <http://www.leonidzhukov.net/hse/2014/socialnetworks/papers/Bonacich-Centrality.pdf>
2: Mark E. J. Newman. Networks: An Introduction. Oxford University Press, USA, 2010, pp. 169.

graphscope.experimental.nx.builtin.katz_centrality(G, alpha=0.1, beta=1.0, max_iter=100, tol=1e-06, nstart=None, normalized=True, weight=None)¶

Compute the Katz centrality for the nodes of the graph G.

Katz centrality computes the centrality for a node based on the centrality of its neighbors. It is a generalization of the eigenvector centrality. The Katz centrality for node $i$ is

\[x_i = \alpha \sum_{j} A_{ij} x_j + \beta,\]

where $A$ is the adjacency matrix of graph G with eigenvalues $lambda$.

The parameter $beta$ controls the initial centrality and

\[\alpha < \frac{1}{\lambda_{\max}}.\]

Katz centrality computes the relative influence of a node within a network by measuring the number of the immediate neighbors (first degree nodes) and also all other nodes in the network that connect to the node under consideration through these immediate neighbors.

Extra weight can be provided to immediate neighbors through the parameter $beta$. Connections made with distant neighbors are, however, penalized by an attenuation factor $alpha$ which should be strictly less than the inverse largest eigenvalue of the adjacency matrix in order for the Katz centrality to be computed correctly. More information is provided in [1]_.

Parameters

G (graph) – A NetworkX graph.
alpha (float) – Attenuation factor
beta (scalar or dictionary, optional (default=1.0)) – Weight attributed to the immediate neighborhood. If not a scalar, the dictionary must have an value for every node.
max_iter (integer, optional (default=1000)) – Maximum number of iterations in power method.
tol (float, optional (default=1.0e-6)) – Error tolerance used to check convergence in power method iteration.
nstart (dictionary, optional) – Starting value of Katz iteration for each node.
normalized (bool, optional (default=True)) – If True normalize the resulting values.
weight (None or string, optional (default=None)) – If None, all edge weights are considered equal. Otherwise holds the name of the edge attribute used as weight.

Returns

nodes – Dictionary of nodes with Katz centrality as the value.

Return type

dictionary

Raises

NetworkXError – If the parameter beta is not a scalar but lacks a value for at least one node
PowerIterationFailedConvergence – If the algorithm fails to converge to the specified tolerance within the specified number of iterations of the power iteration method.

Examples

>>> import math
>>> G = nx.path_graph(4)
>>> phi = (1 + math.sqrt(5)) / 2.0  # largest eigenvalue of adj matrix
>>> centrality = nx.katz_centrality(G, 1 / phi - 0.01)
>>> for n, c in sorted(centrality.items()):
...     print(f"{n} {c:.2f}")
0 0.37
1 0.60
2 0.60
3 0.37

See also

katz_centrality_numpy, eigenvector_centrality, eigenvector_centrality_numpy, pagerank, hits

Notes

Katz centrality was introduced by [2]_.

This algorithm it uses the power method to find the eigenvector corresponding to the largest eigenvalue of the adjacency matrix of G. The parameter alpha should be strictly less than the inverse of largest eigenvalue of the adjacency matrix for the algorithm to converge. You can use max(nx.adjacency_spectrum(G)) to get $lambda_{max}$ the largest eigenvalue of the adjacency matrix. The iteration will stop after max_iter iterations or an error tolerance of number_of_nodes(G) * tol has been reached.

When $alpha = 1/lambda_{max}$ and $beta=0$, Katz centrality is the same as eigenvector centrality.

For directed graphs this finds “left” eigenvectors which corresponds to the in-edges in the graph. For out-edges Katz centrality first reverse the graph with G.reverse().

References

1: Mark E. J. Newman: Networks: An Introduction. Oxford University Press, USA, 2010, p. 720.
2: Leo Katz: A New Status Index Derived from Sociometric Index. Psychometrika 18(1):39–43, 1953 http://phya.snu.ac.kr/~dkim/PRL87278701.pdf

graphscope.experimental.nx.builtin.has_path(G, source, target)¶

Returns True if G has a path from source to target.

Parameters

G (NetworkX graph) –
source (node) – Starting node for path
target (node) – Ending node for path

graphscope.experimental.nx.builtin.shortest_path(G, source=None, target=None, weight=None)¶

Compute shortest paths in the graph.

Parameters

G (NetworkX graph) –
source (node, optional) – Starting node for path. If not specified, compute shortest paths for each possible starting node.
target (node, optional) – Ending node for path. If not specified, compute shortest paths to all possible nodes.
weight (None or string, optional (default = None)) – If None, every edge has weight/distance/cost 1. If a string, use this edge attribute as the edge weight. Any edge attribute not present defaults to 1.
method (string, optional (default = 'dijkstra')) – The algorithm to use to compute the path. Supported options: ‘dijkstra’, ‘bellman-ford’. Other inputs produce a ValueError. If weight is None, unweighted graph methods are used, and this suggestion is ignored.

Returns

path – All returned paths include both the source and target in the path.

If the source and target are both specified, return a single list of nodes in a shortest path from the source to the target.

If only the source is specified, return a dictionary keyed by targets with a list of nodes in a shortest path from the source to one of the targets.

If only the target is specified, return a dictionary keyed by sources with a list of nodes in a shortest path from one of the sources to the target.

If neither the source nor target are specified return a dictionary of dictionaries with path[source][target]=[list of nodes in path].

Return type

list or dictionary

Raises

NodeNotFound – If source is not in G.
ValueError – If method is not among the supported options.

Examples

>>> G = nx.path_graph(5)
>>> print(nx.shortest_path(G, source=0, target=4))
[0, 1, 2, 3, 4]
>>> p = nx.shortest_path(G, source=0)  # target not specified
>>> p[4]
[0, 1, 2, 3, 4]
>>> p = nx.shortest_path(G, target=4)  # source not specified
>>> p[0]
[0, 1, 2, 3, 4]
>>> p = nx.shortest_path(G)  # source, target not specified
>>> p[0][4]
[0, 1, 2, 3, 4]

Notes

There may be more than one shortest path between a source and target. This returns only one of them.

See also

all_pairs_shortest_path, all_pairs_dijkstra_path, all_pairs_bellman_ford_path, single_source_shortest_path, single_source_dijkstra_path, single_source_bellman_ford_path

graphscope.experimental.nx.builtin.single_source_dijkstra_path_length(G, source, weight=None)¶

Find shortest weighted path lengths in G from a source node.

Compute the shortest path length between source and all other reachable nodes for a weighted graph.

Parameters

G (NetworkX graph) –
source (node label) – Starting node for path
cutoff (integer or float, optional) – Depth to stop the search. Only return paths with length <= cutoff.
weight (string or function) –
If this is a string, then edge weights will be accessed via the edge attribute with this key (that is, the weight of the edge joining u to v will be G.edges[u, v][weight]). If no such edge attribute exists, the weight of the edge is assumed to be one.

If this is a function, the weight of an edge is the value returned by the function. The function must accept exactly three positional arguments: the two endpoints of an edge and the dictionary of edge attributes for that edge. The function must return a number.

Returns

length – Dict keyed by node to shortest path length from source.

Return type

dict

Raises

NodeNotFound – If source is not in G.

Examples

>>> G = nx.path_graph(5)
>>> length = nx.single_source_dijkstra_path_length(G, 0)
>>> length[4]
4
>>> for node in [0, 1, 2, 3, 4]:
...     print(f"{node}: {length[node]}")
0: 0
1: 1
2: 2
3: 3
4: 4

Notes

Edge weight attributes must be numerical. Distances are calculated as sums of weighted edges traversed.

The weight function can be used to hide edges by returning None. So weight = lambda u, v, d: 1 if d['color']=="red" else None will find the shortest red path.

See also

single_source_dijkstra, single_source_bellman_ford_path_length

graphscope.experimental.nx.builtin.average_shortest_path_length(G, weight=None)¶

Returns the average shortest path length.

The average shortest path length is

\[a =\sum_{s,t \in V} \frac{d(s, t)}{n(n-1)}\]

where V is the set of nodes in G, d(s, t) is the shortest path from s to t, and n is the number of nodes in G.

Parameters

G (NetworkX graph) –
weight (None or string, optional (default = None)) – If None, every edge has weight/distance/cost 1. If a string, use this edge attribute as the edge weight. Any edge attribute not present defaults to 1.
method (string, optional (default = 'unweighted' or 'djikstra')) – The algorithm to use to compute the path lengths. Supported options are ‘unweighted’, ‘dijkstra’, ‘bellman-ford’, ‘floyd-warshall’ and ‘floyd-warshall-numpy’. Other method values produce a ValueError. The default method is ‘unweighted’ if weight is None, otherwise the default method is ‘dijkstra’.

Raises

NetworkXPointlessConcept – If G is the null graph (that is, the graph on zero nodes).
NetworkXError – If G is not connected (or not weakly connected, in the case of a directed graph).
ValueError – If method is not among the supported options.

Examples

>>> G = nx.path_graph(5)
>>> nx.average_shortest_path_length(G)
2.0

For disconnected graphs, you can compute the average shortest path length for each component

>>> G = nx.Graph([(1, 2), (3, 4)])
>>> for C in (G.subgraph(c).copy() for c in nx.connected_components(G)):
...     print(nx.average_shortest_path_length(C))
1.0
1.0

graphscope.experimental.nx.builtin.bfs_edges(G, source, reverse=False, depth_limit=None)¶

Iterate over edges in a breadth-first-search starting at source.

Parameters

G (NetworkX graph) –
source (node) – Specify starting node for breadth-first search; this function iterates over only those edges in the component reachable from this node.
reverse (bool, optional) – If True traverse a directed graph in the reverse direction
depth_limit (int, optional(default=len(G))) – Specify the maximum search depth
sort_neighbors (function) – A function that takes the list of neighbors of given node as input, and returns an iterator over these neighbors but with custom ordering.

Returns

edges – A generator of edges in the breadth-first-search.

Return type

generator

Examples

To get the edges in a breadth-first search:

>>> G = nx.path_graph(3)
>>> list(nx.bfs_edges(G, 0))
[(0, 1), (1, 2)]
>>> list(nx.bfs_edges(G, source=0, depth_limit=1))
[(0, 1)]

To get the nodes in a breadth-first search order:

>>> G = nx.path_graph(3)
>>> root = 2
>>> edges = nx.bfs_edges(G, root)
>>> nodes = [root] + [v for u, v in edges]
>>> nodes
[2, 1, 0]

Notes

The naming of this function is very similar to edge_bfs. The difference is that ‘edge_bfs’ yields edges even if they extend back to an already explored node while ‘bfs_edges’ yields the edges of the tree that results from a breadth-first-search (BFS) so no edges are reported if they extend to already explored nodes. That means ‘edge_bfs’ reports all edges while ‘bfs_edges’ only reports those traversed by a node-based BFS. Yet another description is that ‘bfs_edges’ reports the edges traversed during BFS while ‘edge_bfs’ reports all edges in the order they are explored.

Based on http://www.ics.uci.edu/~eppstein/PADS/BFS.py. by D. Eppstein, July 2004. The modifications to allow depth limits based on the Wikipedia article “Depth-limited-search”.

See also

bfs_tree, dfs_edges, edge_bfs

graphscope.experimental.nx.builtin.bfs_predecessors(G, source, depth_limit=None)¶

Returns an iterator of predecessors in breadth-first-search from source.

Parameters

G (NetworkX graph) –
source (node) – Specify starting node for breadth-first search
depth_limit (int, optional(default=len(G))) – Specify the maximum search depth
sort_neighbors (function) – A function that takes the list of neighbors of given node as input, and returns an iterator over these neighbors but with custom ordering.

Returns

pred – (node, predecessors) iterator where predecessors is the list of predecessors of the node.

Return type

iterator

Examples

>>> G = nx.path_graph(3)
>>> print(dict(nx.bfs_predecessors(G, 0)))
{1: 0, 2: 1}
>>> H = nx.Graph()
>>> H.add_edges_from([(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)])
>>> print(dict(nx.bfs_predecessors(H, 0)))
{1: 0, 2: 0, 3: 1, 4: 1, 5: 2, 6: 2}
>>> M = nx.Graph()
>>> nx.add_path(M, [0, 1, 2, 3, 4, 5, 6])
>>> nx.add_path(M, [2, 7, 8, 9, 10])
>>> print(sorted(nx.bfs_predecessors(M, source=1, depth_limit=3)))
[(0, 1), (2, 1), (3, 2), (4, 3), (7, 2), (8, 7)]

Notes

Based on http://www.ics.uci.edu/~eppstein/PADS/BFS.py by D. Eppstein, July 2004. The modifications to allow depth limits based on the Wikipedia article “Depth-limited-search”.

See also

bfs_tree, bfs_edges, edge_bfs

graphscope.experimental.nx.builtin.bfs_successors(G, source, depth_limit=None)¶

Returns an iterator of successors in breadth-first-search from source.

Parameters

G (NetworkX graph) –
source (node) – Specify starting node for breadth-first search
depth_limit (int, optional(default=len(G))) – Specify the maximum search depth
sort_neighbors (function) – A function that takes the list of neighbors of given node as input, and returns an iterator over these neighbors but with custom ordering.

Returns

succ – (node, successors) iterator where successors is the list of successors of the node.

Return type

iterator

Examples

>>> G = nx.path_graph(3)
>>> print(dict(nx.bfs_successors(G, 0)))
{0: [1], 1: [2]}
>>> H = nx.Graph()
>>> H.add_edges_from([(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)])
>>> print(dict(nx.bfs_successors(H, 0)))
{0: [1, 2], 1: [3, 4], 2: [5, 6]}
>>> G = nx.Graph()
>>> nx.add_path(G, [0, 1, 2, 3, 4, 5, 6])
>>> nx.add_path(G, [2, 7, 8, 9, 10])
>>> print(dict(nx.bfs_successors(G, source=1, depth_limit=3)))
{1: [0, 2], 2: [3, 7], 3: [4], 7: [8]}

Notes

Based on http://www.ics.uci.edu/~eppstein/PADS/BFS.py by D. Eppstein, July 2004.The modifications to allow depth limits based on the Wikipedia article “Depth-limited-search”.

See also

bfs_tree, bfs_edges, edge_bfs

graphscope.experimental.nx.builtin.k_core(G, k=None, core_number=None)¶

Returns the k-core of G.

A k-core is a maximal subgraph that contains nodes of degree k or more.

Parameters

G (NetworkX graph) – A graph or directed graph
k (int, optional) – The order of the core. If not specified return the main core.
core_number (dictionary, optional) – Precomputed core numbers for the graph G.

Returns

G – The k-core subgraph

Return type

NetworkX graph

Raises

NetworkXError – The k-core is not defined for graphs with self loops or parallel edges.

Notes

The main core is the core with the largest degree.

Not implemented for graphs with parallel edges or self loops.

For directed graphs the node degree is defined to be the in-degree + out-degree.

Graph, node, and edge attributes are copied to the subgraph.

See also

core_number

References

1: An O(m) Algorithm for Cores Decomposition of Networks Vladimir Batagelj and Matjaz Zaversnik, 2003. https://arxiv.org/abs/cs.DS/0310049

graphscope.experimental.nx.builtin.clustering(G, nodes=None, weight=None)¶

Compute the clustering coefficient for nodes.

For unweighted graphs, the clustering of a node $u$ is the fraction of possible triangles through that node that exist,

\[c_u = \frac{2 T(u)}{deg(u)(deg(u)-1)},\]

where $T(u)$ is the number of triangles through node $u$ and $deg(u)$ is the degree of $u$.

For weighted graphs, there are several ways to define clustering [1]_. the one used here is defined as the geometric average of the subgraph edge weights [2]_,

\[c_u = \frac{1}{deg(u)(deg(u)-1))} \sum_{vw} (\hat{w}_{uv} \hat{w}_{uw} \hat{w}_{vw})^{1/3}.\]

The edge weights $\hat{w}_{uv}$ are normalized by the maximum weight in the network $\hat{w}_{uv} = w_{uv}/\max(w)$.

The value of $c_u$ is assigned to 0 if $deg(u) < 2$.

For directed graphs, the clustering is similarly defined as the fraction of all possible directed triangles or geometric average of the subgraph edge weights for unweighted and weighted directed graph respectively 3.

\[c_u = \frac{1}{deg^{tot}(u)(deg^{tot}(u)-1) - 2deg^{\leftrightarrow}(u)} T(u),\]

where $T(u)$ is the number of directed triangles through node $u$, $deg^{tot}(u)$ is the sum of in degree and out degree of $u$ and $deg^{\leftrightarrow}(u)$ is the reciprocal degree of $u$.

Parameters

G (graph) –
nodes (container of nodes, optional (default=all nodes in G)) – Compute clustering for nodes in this container.
weight (string or None, optional (default=None)) – The edge attribute that holds the numerical value used as a weight. If None, then each edge has weight 1.

Returns

out – Clustering coefficient at specified nodes

Return type

float, or dictionary

Examples

>>> G = nx.complete_graph(5)
>>> print(nx.clustering(G, 0))
1.0
>>> print(nx.clustering(G))
{0: 1.0, 1: 1.0, 2: 1.0, 3: 1.0, 4: 1.0}

Notes

Self loops are ignored.

References

1: Generalizations of the clustering coefficient to weighted complex networks by J. Saramäki, M. Kivelä, J.-P. Onnela, K. Kaski, and J. Kertész, Physical Review E, 75 027105 (2007). http://jponnela.com/web_documents/a9.pdf
2: Intensity and coherence of motifs in weighted complex networks by J. P. Onnela, J. Saramäki, J. Kertész, and K. Kaski, Physical Review E, 71(6), 065103 (2005).
3: Clustering in complex directed networks by G. Fagiolo, Physical Review E, 76(2), 026107 (2007).

graphscope.experimental.nx.builtin.triangles(G, nodes=None)¶

Compute the number of triangles.

Finds the number of triangles that include a node as one vertex.

Parameters

G (graph) – A networkx graph
nodes (container of nodes, optional (default= all nodes in G)) – Compute triangles for nodes in this container.

Returns

out – Number of triangles keyed by node label.

Return type

dictionary

Examples

>>> G = nx.complete_graph(5)
>>> print(nx.triangles(G, 0))
6
>>> print(nx.triangles(G))
{0: 6, 1: 6, 2: 6, 3: 6, 4: 6}
>>> print(list(nx.triangles(G, (0, 1)).values()))
[6, 6]

Notes

When computing triangles for the entire graph each triangle is counted three times, once at each node. Self loops are ignored.

graphscope.experimental.nx.builtin.transitivity(G)¶

Compute graph transitivity, the fraction of all possible triangles present in G.

Possible triangles are identified by the number of “triads” (two edges with a shared vertex).

The transitivity is

\[T = 3\frac{\#triangles}{\#triads}.\]

Parameters: G (graph) –
Returns: out – Transitivity
Return type: float

Examples

>>> G = nx.complete_graph(5)
>>> print(nx.transitivity(G))
1.0

graphscope.experimental.nx.builtin.average_clustering(G, nodes=None, weight=None, count_zeros=True)¶

Compute the average clustering coefficient for the graph G.

The clustering coefficient for the graph is the average,

\[C = \frac{1}{n}\sum_{v \in G} c_v,\]

where $n$ is the number of nodes in G.

Parameters

G (graph) –
nodes (container of nodes, optional (default=all nodes in G)) – Compute average clustering for nodes in this container.
weight (string or None, optional (default=None)) – The edge attribute that holds the numerical value used as a weight. If None, then each edge has weight 1.
count_zeros (bool) – If False include only the nodes with nonzero clustering in the average.

Returns

avg – Average clustering

Return type

float

Examples

>>> G = nx.complete_graph(5)
>>> print(nx.average_clustering(G))
1.0

Notes

This is a space saving routine; it might be faster to use the clustering function to get a list and then take the average.

Self loops are ignored.

References

1: Generalizations of the clustering coefficient to weighted complex networks by J. Saramäki, M. Kivelä, J.-P. Onnela, K. Kaski, and J. Kertész, Physical Review E, 75 027105 (2007). http://jponnela.com/web_documents/a9.pdf
2: Marcus Kaiser, Mean clustering coefficients: the role of isolated nodes and leafs on clustering measures for small-world networks. https://arxiv.org/abs/0802.2512