Builtin algorithms

graphscope.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.
normalized (bool (default=True)) – Normalize results by the sum of all of the values.

Returns

Return type

two-tuple of dictionaries

Examples

>>> G = nx.path_graph(4)
>>> nx.hits(G)

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.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

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.nx.builtin.eigenvector_centrality(G, max_iter=100, tol=1e-06, weight=None)

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

graphscope.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.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}\]

rac{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.

G : networkx graph

weightNone or string, optional (default = None)
If None, default take as ‘weight’. If a string, use this edge attribute as the edge weight.
>>> G = nx.path_graph(5)
>>> nx.average_shortest_path_length(G)
2.0

graphscope.nx.builtin.bfs_edges(G, source, depth_limit=None)

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.
depth_limit (int, optional(default=len(G))) – Specify the maximum search depth

Returns

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

Return type

list

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)]

graphscope.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.

Returns

:class:`VertexDataContext` (A context with each vertex assigned with a boolean:)
1 if the vertex satisfies k-core, otherwise 0.

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.nx.builtin.clustering(G)

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) –
Returns: out – Clustering coefficient at nodes
Return type: dataframe

Examples

>>> G = nx.path_graph(5)
>>>nx.clustering(G)

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.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
Returns: out – Number of triangles keyed by node label.
Return type: dataframe

Notes

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

graphscope.nx.builtin.average_clustering(G, nodes=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