easygraph.functions.community package

Submodules

easygraph.functions.community.LPA module

easygraph.functions.community.LPA.BMLPA(G, p)

Detect community by Balanced Multi-Label Propagation algorithm

Return the detected communities.

Firstly, initialize ‘old’ using cores generated by RC function, the propagate label till the number and size of communities stay no change, check if there are subcommunity and delete it. Finally, split discontinuous communities.

For some directed graphs lead to oscillations of labels, modify the stop condition.

Parameters:

• G (graph) – A easygraph graph

• p (float) – Between 0 and 1, judge Whether a community identifier should be retained

Returns:

communities – key: serial number of community , value: nodes in the community.

Return type:

dictionary

Examples

>>> BMLPA(G,
...     p = 0.1,
...     )

References

[1]

Wu Zhihao, Lin You-Fang, Gregory Steve, Wan Huai-Yu, Tian Sheng-Feng Balanced Multi-Label Propagation for Overlapping Community Detection in Social Networks

easygraph.functions.community.LPA.HANP(G, m, delta, threshod=1, hier_open=0, combine_open=0)

Detect community by Hop attenuation & node preference algorithm

Return the detected communities. But the result is random.

Implement the basic HANP algorithm and give more freedom through the parameters, e.g., you can use threshod to set the condition for node updating. If network are known to be Hierarchical and overlapping communities, it’s recommended to choose geodesic distance as the measure(instead of receiving the current hop scores from the neighborhood and carry out a subtraction) and When an equilibrium is reached, treat newly combined communities as a single node.

For using Floyd to get the shortest distance, the time complexity is a little high.

Parameters:

• G (graph) – A easygraph graph

• m (float) – Used to calculate score, when m > 0, more preference is given to node with more neighbors; m < 0, less

• delta (float) – Hop attenuation

• threshod (float) – Between 0 and 1, only update node whose number of neighbors sharing the maximal label is less than the threshod. e.g., threshod == 1 means updating all nodes.

• hier_open – 1 means using geodesic distance as the score measure. 0 means not.

• combine_open – this option is valid only when hier_open = 1 1 means When an equilibrium is reached, treat newly combined communities as a single node. 0 means not.

Returns:

communities – key: serial number of community , value: nodes in the community.

Return type:

dictionary

Examples

>>> HANP(G,
...     m = 0.1,
...     delta = 0.05,
...     threshod = 1,
...     hier_open = 0,
...     combine_open = 0
...     )

References

[1]

Ian X. Y. Leung, Pan Hui, Pietro Liò, and Jon Crowcrof: Towards real-time community detection in large networks

easygraph.functions.community.LPA.LPA(G)

Detect community by label propagation algorithm Return the detected communities. But the result is random. Each node in the network is initially assigned to its own community. At every iteration,nodes have a label that the maximum number of their neighbors have. If there are more than one nodes fit and available, choose a label randomly. Finally, nodes having the same labels are grouped together as communities. In case two or more disconnected groups of nodes have the same label, we run a simple breadth-first search to separate the disconnected communities

Parameters:

G (graph) – A easygraph graph

Returns:

communities – key: serial number of community , value: nodes in the community.

Return type:

dictionary

Examples

>>> LPA(G)

References

[1]

Usha Nandini Raghavan, Réka Albert, and Soundar Kumara: Near linear time algorithm to detect community structures in large-scale networks

easygraph.functions.community.LPA.SLPA(G, T, r)

Detect Overlapping Communities by Speaker-listener Label Propagation Algorithm Return the detected Overlapping communities. But the result is random.

Parameters:

• G (graph) – A easygraph graph.

• T (int) – The number of iterations, In general, T is set greater than 20, which produces relatively stable outputs.

• r (int) – a threshold between 0 and 1.

Returns:

communities – key: serial number of community , value: nodes in the community.

Return type:

dictionary

Examples

>>> SLPA(G,
...     T = 20,
...     r = 0.05
...     )

References

[1]

Jierui Xie, Boleslaw K. Szymanski, Xiaoming Liu: SLPA: Uncovering Overlapping Communities in Social Networks via A Speaker-listener Interaction Dynamic Process

easygraph.functions.community.ego_graph module

easygraph.functions.community.louvain module

easygraph.functions.community.modularity module

easygraph.functions.community.modularity.modularity(G, communities, weight='weight')

Returns the modularity of the given partition of the graph. Modularity is defined in [1]_ as

\[Q = \frac{1}{2m} \sum_{ij} \left( A_{ij} - \frac{k_ik_j}{2m}\right) \delta(c_i,c_j)\]

where m is the number of edges, A is the adjacency matrix of G,

\[k_i\ is\ the\ degree\ of\ i\ and\ \delta(c_i, c_j)\ is\ 1\ if\ i\ and\ j\ are\ in\ the\ same\ community\ and\ 0\ otherwise.\]

Parameters:

• G (easygraph.Graph or easygraph.DiGraph) –

• communities (list or iterable of set of nodes) – These node sets must represent a partition of G’s nodes.

• weight (string, optional (default : 'weight')) – The key for edge weight.

Returns:

Q – The modularity of the partition.

Return type:

float

References

[1]

M. E. J. Newman Networks: An Introduction, page 224. Oxford University Press, 2011.

easygraph.functions.community.modularity_max_detection module

easygraph.functions.community.modularity_max_detection.greedy_modularity_communities(G, weight='weight')

Communities detection via greedy modularity method.

Find communities in graph using Clauset-Newman-Moore greedy modularity maximization. This method currently supports the Graph class.

Greedy modularity maximization begins with each node in its own community and joins the pair of communities that most increases modularity until no such pair exists.

Parameters:

• G (easygraph.Graph or easygraph.DiGraph) –

• weight (string (default : 'weight')) – The key for edge weight. For undirected graph, it will regard each edge weight as 1.

Return type:

Yields sets of nodes, one for each community.

References

[1]

Newman, M. E. J. “Networks: An Introduction Oxford Univ.” (2010).

[2]

Clauset, Aaron, Mark EJ Newman, and Cristopher Moore.

“Finding community structure in very large networks.” Physical review E 70.6 (2004): 066111.

easygraph.functions.community.motif module

easygraph.functions.community.motif.enumerate_subgraph(G, k: int)

Returns the motifs. Motifs are small weakly connected induced subgraphs of a given structure in a graph.

Parameters:

• G (easygraph.Graph or easygraph.DiGraph.) –

• k (int) – The size of the motifs to search for.

Returns:

k_subgraphs – The motifs.

Return type:

list

References

[1]

Wernicke, Sebastian. “Efficient detection of network motifs.” IEEE/ACM transactions on computational biology and bioinformatics 3.4 (2006): 347-359.

easygraph.functions.community.motif.random_enumerate_subgraph(G, k: int, cut_prob: list)

Returns the motifs. Motifs are small weakly connected induced subgraphs of a given structure in a graph.

Parameters:

• G (easygraph.Graph or easygraph.DiGraph.) –

• k (int) – The size of the motifs to search for.

• cut_prob (list) – list of probabilities for cutting the search tree at a given level.

Returns:

k_subgraphs – The motifs.

Return type:

list

References

[1]

Wernicke, Sebastian. “A faster algorithm for detecting network motifs.”

International Workshop on Algorithms in Bioinformatics. Springer, Berlin, Heidelberg, 2005.

Module contents