Academic Journal of Computing & Information Science, 2021, 4(1); doi: 10.25236/AJCIS.2021.040101.
Ye Zhu, Jun Gong, Simeng Wu
School of Software, Jiangxi Normal University, Jiangxi Province, China
Centrality is a measure index evaluating node and edge importance, and edge betweenness centrality is the most important among those. The length of shortest path between two nodes shows their relationship. When the path is longer, their relationship is weaker. Based on this idea, this paper think that two nodes have no relationship beyond some range. This paper introduces local edge betweenness centrality within K steps and weight of path length, and puts forward a new centrality evaluation method. Based on this, our method utilizes the core idea of GN algorithm, and puts forward a new community detection algorithm called Dist-K. Its performance and result are compared with other existing methods, as applied to different well-known instances of complex networks. Our method has better modularity, normalized mutual information, adjusted rand index and accuracy, which are widely used to measure community structures.
local edge betweenness centrality, community detection, path length
Ye Zhu, Jun Gong, Simeng Wu. An Efficient Community Detection Method Based on Path Proximity and Local Edge Betweenness Centrality. Academic Journal of Computing & Information Science (2021), Vol. 4, Issue 1: 1-6. https://doi.org/10.25236/AJCIS.2021.040101.
[1] Pàl Erds, A. R. Rényi. On random graphs I [J]. Publicationes Mathematicae, 1959, 6: 290-297.
[2] Watts D, Strogatz S. Collective dynamics of 'small-world' networks [J]. Nature, 1998, 393 (6684): P.440-442.
[3] Barabasi A L, Albert R. Albert, R.: Emergence of Scaling in Random Networks. Science 286, 509-512 [J]. ence, 1999, 286 (5439): 509-512.
[4] Merrer EL, Tredan G. Centralities: Capturing the fuzzy notion of importance in social graphs. In: Proc. of the European Conf. on Computer Systems. 2009. 33-38 [doi:10.1145/1578002.1578008]
[5] Newman M E. Fast algorithm for detecting community structure in networks[J]. Phys Rev E Stat Nonlin Soft Matter Phys, 2004, 69(6 Pt 2): 066133.
[6] Vinh N X, Epps J, Bailey J. Information Theoretic Measures for Clusterings Comparison: Variants, Properties, Normalization and Correction for Chance [M]. JMLR.org, 2010.
[7] Danon L, Duch J, Diaz-Guilera A, et al. Comparing community structure identification [J]. Journal of Statal Mechanics, 2005, 2005 (09): 09008.
[8] Wayne, W, Zachary. An Information Flow Model for Conflict and Fission in Small Groups [J]. Journal of Anthropological Research, 1977.
[9] Lusseau D, Schneider K, Boisseau O J, et al. The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations [J]. Behavioral Ecology & Sociobiology, 2003, 54 (4): 396-405.
[10] Lusseau D, Newman M E J. Identifying the role that animals play in their social networks. [J]. Proceedings of the Royal Society B Biological ences, 2004, 271 (Suppl_6): S477.
[11] Shen H W. Community Structure of Complex Networks [J]. Complex Systems and Complexity ence, 2011.
[12] Newman M E J. Modularity and community structure in networks [C] // 2006 APS March Meeting. American Physical Society, 2006.