easygraph.functions.community.LPA module#

easygraph.functions.community.LPA.BMLPA(G, p)[source]#

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)[source]#

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)[source]#

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)[source]#

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