easygraph.functions.basic package

Submodules

easygraph.functions.basic.avg_degree module

easygraph.functions.basic.avg_degree.average_degree(G) → float[source]

Returns the average degree of the graph.

Parameters

G (graph) – A EasyGraph graph

Returns

average degree – The average degree of the graph.

Return type

float

Notes

Self loops are counted twice in the total degree of a node.

Examples

>>> G = eg.Graph()  # or DiGraph, MultiGraph, MultiDiGraph, etc
>>> G.add_edge(1, 2)
>>> G.add_edge(2, 3)
>>> eg.average_degree(G)
1.3333333333333333

easygraph.functions.basic.cluster module

easygraph.functions.basic.cluster.average_clustering(G, nodes=None, weight=None, count_zeros=True, n_workers=None)[source]

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 = eg.complete_graph(5)
>>> print(eg.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

easygraph.functions.basic.cluster.clustering(G, nodes=None, weight=None, n_workers=None)[source]

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

Additionally, this weighted definition has been generalized to support negative edge weights 3.

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

\[c_u = \frac{2}{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 = eg.complete_graph(5)
>>> print(eg.clustering(G, 0))
1.0
>>> print(eg.clustering(G))
{0: 1.0, 1: 1.0, 2: 1.0, 3: 1.0, 4: 1.0}

Notes

Self loops are ignored.

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

Generalization of Clustering Coefficients to Signed Correlation Networks by G. Costantini and M. Perugini, PloS one, 9(2), e88669 (2014).

4

Clustering in complex directed networks by G. Fagiolo, Physical Review E, 76(2), 026107 (2007).

easygraph.functions.basic.localassort module

easygraph.functions.basic.localassort.localAssort(edgelist, node_attr, pr=array([0., 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9]), undir=True, missingValue=-1)[source]

Calculate the multiscale assortativity. You must ensure that the node index and node attribute index start from 0 :param edgelist: the network represented as an edge list,

i.e., a E x 2 array of node pairs

Parameters

  • node_attr (array_like) – n length array of node attribute values

  • pr (array, optional) – array of one minus restart probabilities for the random walk in calculating the personalised pagerank. The largest of these values determines the accuracy of the TotalRank vector max(pr) -> 1 is more accurate (default: [0, .1, .2, .3, .4, .5, .6, .7, .8, .9])

  • undir (bool, optional) – indicate if network is undirected (default: True)

  • missingValue (int, optional) – token to indicate missing attribute values (default: -1)

Returns

  • assortM (array_like) – n x len(pr) array of local assortativities, each column corresponds to a value of the input restart probabilities, pr. Note if only number of restart probabilties is greater than one (i.e., len(pr) > 1).

  • assortT (array_like) – n length array of multiscale assortativities

  • Z (array_like) – N length array of per-node confidence scores

References

For full details see [1]_ .. [1] Peel, L., Delvenne, J. C., & Lambiotte, R. (2018). “Multiscale

mixing patterns in networks.’ PNAS, 115(16), 4057-4062.

easygraph.functions.basic.predecessor_path_based module

easygraph.functions.basic.predecessor_path_based.predecessor(G, source, target=None, cutoff=None, return_seen=None)[source]

Returns dict of predecessors for the path from source to all nodes in G.

Parameters

  • G (EasyGraph graph) –

  • source (node label) – Starting node for path

  • target (node label, optional) – Ending node for path. If provided only predecessors between source and target are returned

  • cutoff (integer, optional) – Depth to stop the search. Only paths of length <= cutoff are returned.

  • return_seen (bool, optional (default=None)) – Whether to return a dictionary, keyed by node, of the level (number of hops) to reach the node (as seen during breadth-first-search).

Returns

pred – Dictionary, keyed by node, of predecessors in the shortest path.

Return type

dictionary

(pred, seen): tuple of dictionaries

If return_seen argument is set to True, then a tuple of dictionaries is returned. The first element is the dictionary, keyed by node, of predecessors in the shortest path. The second element is the dictionary, keyed by node, of the level (number of hops) to reach the node (as seen during breadth-first-search).

Examples

>>> G = eg.path_graph(4)
>>> list(G)
[0, 1, 2, 3]
>>> eg.predecessor(G, 0)
{0: [], 1: [0], 2: [1], 3: [2]}
>>> eg.predecessor(G, 0, return_seen=True)
({0: [], 1: [0], 2: [1], 3: [2]}, {0: 0, 1: 1, 2: 2, 3: 3})

Module contents