In recent years, community structure has become a research hotspot in complex networks, and there are currently many excellent methods in the field of community detection, such as label propagation algorithms, LFM community detection algorithms, etc. These algorithms primarily investigate undirected networks, but the linking relationships between nodes in real complex networks are mostly directed and asymmetric, such as social networks. Therefore it is imperative to perform community detection on directed networks. We proposed a locally expansion community detection algorithm (DLE-NL) that can be applied to directed networks. There are four essential parts of DLE-NL algorithm: Firstly, the node cross-leadership index is proposed to select seed nodes considering local and global factors and directionality; secondly, seed node confidants are chosen to form the initial community using node following degree, and the core of the community is precisely mined; then node aggregation is carried out considering the node affiliation to the community with the initial community as the core. Finally, the initial reconstruction and optimization of the community are carried out by removing communities with less than three nodes, correcting the affiliation of nodes to the community based on the community directed-fitness function and the gain of the derivative, assigning free nodes and merging communities with high similarity. The experimental results show that the method performs well in the directed modularity and normalized mutual information metrics, while the community detection results are more stable.

Fei Liu, Jun Gong, Laizong Huang, Shibin Li. Locally Expansion Directed Community Detection Method Considering Node Leadership. Academic Journal of Computing & Information Science (2022), Vol. 5, Issue 11: 79-84. https://doi.org/10.25236/AJCIS.2022.051112.

[1] AL Barabá si. The New Science of Networks [J]. Physics Today, 2003, 6(5): 444. 

[2] Schölkopf B, Hofmann T, Zhou D. Semi-supervised learning on directed graphs [J]. Nips, 2005, 17(2005):1633-1640.

[3] Guimerà R, Sales-Pardo M, Amaral L A N. Module identification in bipartite and directed networks [J]. Physical Review E, 2007, 76(3): 036102.

[4] Lai D, Lu H, Nardini C. Finding communities in directed networks by PageRank random walk induced network embedding [J]. Physica A Statistical Mechanics & Its Applications, 2010, 389(12):2443-2454.

[5] Cooper K, Barahona M. Role-based similarity in directed networks [J]. Physics, 2010.1012(2726): 1-4.

[6] Satuluri V, Parthasarathy S. Symmetrizations for clustering directed graphs[C]. Proceedings of the 14th International Conference on Extending Database Technology. ACM, 2011: 343-354.

[7] Leicht E A, Newman M E J. Community structure in directed networks[J]. Physical Review Letters, 2008, 100(11): 2339-2340.

[8] Kim Y, Son S W, Jeong H. Finding communities in directed networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2009, 81(1):016103.

[9] Meilă M, Pentney W. Clustering by weighted cuts in directed graphs[C]. Proceedings of the 2007 SIAM international conference on data mining. Society for Industrial and Applied Mathematics, 2007: 135-144.

[10] Liu S G. Detecting communities of directed networks via a local algorithm[J]. J. Math. Inform, 2013, 1: 43-51.

[11] Chen W Y, Song Y, Bai H, et al. Parallel spectral clustering in distributed systems.[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2011, 33(3):568-586.

[12] Lancichinetti A, Fortunato S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities [J]. Physical Review E, 2009, 80(1):016118.

[13] Lidong Fu, Dan Li, Zhanli Li. The membership tree algorithm detects overlapping communities in complex networks [J]. Computer Science, 2019, 46 (12): 330-334.

[14] Newman M, Girvan M. Finding and Evaluating Community Structure in Networks[J]. Physical Review E, 2004, 69(2 Pt 2):026113.

[15] Newman M, Clauset A. Structure and inference in annotated networks[J]. Nature Communications, 2015, 7(2-3):11863.