Overlapping communities exist in real networks, where the communities represent hierarchical community structures, such as schools and government departments. A non-binary tree allows a vertex to belong to multiple communities to obtain a more realistic overlapping community structure. It is challenging to select appropriate leaf vertices and construct a hierarchical tree that considers a large amount of structural information. In this paper, we propose a non-binary hierarchical tree overlapping community detection based on multi-dimensional similarity. The multi-dimensional similarity fully considers the local structure characteristics between vertices to calculate the similarity between vertices. First, we construct a similarity matrix based on the first and second-order neighbor vertices and select a leaf vertex. Second, we expand the leaf vertex based on the principle of maximum community density and construct a non-binary tree. Finally, we choose the layer with the largest overlapping modularity as the result of community division. Experiments on real-world networks demonstrate that our proposed algorithm is superior to other representative algorithms in terms of the quality of overlapping community detection.
BickelP.J. and ChenA., A nonparametric view of network models and NewmanCGirvan and other modularities, Proceedings of the National Academy of Sciences106(50) (2009), 21068–21073.
2.
HeD.JinD.BaqueroC. et al., Link community detection using generative model and nonnegative matrix factorization, PloS One9(1) (2014).
3.
PallaG.DernyiI.FarkasI. et al., Uncovering the overlapping community structure of complex networks in nature and society, Nature435(7043) (2005), 814–818.
4.
KumpulaJ.M.KivelM.KaskiK. et al., Sequential algorithm for fast clique percolation, Physical Review E78(2) (2008), 026109.
5.
WhangJ.J.GleichD.F. and DhillonI.S., Overlapping community detection using neighborhood-inflated seed expansion, IEEE Transactions on Knowledge and Data Engineering28(5) (2016), 1272–1284.
6.
ZhangJ.DingX. and YangJ., Revealing the role of node similarity and community merging in community detection, Knowledge-Based Systems165 (2019), 407–419.
7.
ChenQ.WuT.T. and FangM., Detecting local community structures in complex networks based on local degree central nodes, Physica A: Statistical Mechanics and its Applications392(3) (2013), 529–537.
8.
XieJ.SzymanskiB.K. and LiuX., Slpa: Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process, in: 2011 Ieee 11th International Conference on Data Mining Workshops, IEEE, 2011, pp. 344–349.
9.
CosciaM.RossettiG.GiannottiF. et al., Demon: a local-first discovery method for overlapping communities, in: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2012, pp. 615–623.
10.
LiY.HeK.KlosterK. et al., Local spectral clustering for overlapping community detection, ACM Transactions on Knowledge Discovery from Data (TKDD)12(2) (2018), 1–27.
11.
SunZ.WangB.ShengJ. et al., Overlapping community detection based on information dynamics, IEEE Access6 (2018), 70919–70934.
12.
BaumesJ.GoldbergM.K.KrishnamoorthyM.S. et al., Finding communities by clustering a graph into overlapping subgraphs, IADIS AC5 (2005), 97–104.
13.
ChenN.LiuY. and ChaoH.C., Overlapping community detection using non-negative matrix factorization with orthogonal and sparseness constraints, IEEE Access6 (2017), 21266–21274.
14.
YangJ. and LeskovecJ., Overlapping community detection at scale: a nonnegative matrix factorization approach, in: Proceedings of the sixth ACM International Conference on Web Search and Data Mining, 2013, pp. 587–596.
15.
LancichinettiA.FortunatoS. and KertszJ., Detecting the overlapping and hierarchical community structure in complex networks, New Journal of Physics11(3) (2009), 033015.
16.
ShenH.ChengX.CaiK. et al., Detect overlapping and hierarchical community structure in networks, Physica A: Statistical Mechanics and its Applications388(8) (2009), 1706–1712.
17.
ZhaoY.LiS. and WangS., Agglomerative clustering based on label propagation for detecting overlapping and hierarchical communities in complex networks, Advances in Complex Systems17(6) (2014), 1450021.
18.
ZhangL.PanH.SuY. et al., A mixed representation based multiobjective evolutionary algorithm for overlapping community detection, IEEE Transactions on Cybernetics47(9) (2017), 2703–2716.
19.
GongM.ChenX.MaL. et al., Identification of multi-resolution network structures with multi-objective immune algorithm, Applied Soft Computing13(4) (2013), 1705–1717.
20.
WuB.WuS. and LiuX., Optimization on GA-BP neural network of coal and gas outburst hazard prediction, in: 2010 IEEE Fifth International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA), IEEE, 2010, pp. 673–678.
21.
MuC.H.XieJ.LiuY. et al., Memetic algorithm with simulated annealing strategy and tightness greedy optimization for community detection in networks, Applied Soft Computing34 (2015), 485–501.
22.
CaiQ.GongM.MaL. et al., Greedy discrete particle swarm optimization for large-scale social network clustering, Information Sciences316 (2015), 503–516.
23.
ZhaoP. and ZhangC.Q., A new clustering method and its application in social networks, Pattern Recognition Letters32(15) (2011), 2109–2118.
24.
ZacharyW.W., An information flow model for conflict and fission in small groups, Journal of Anthropological Research33(4) (1977), 452–473.
25.
LusseauD., The emergent properties of a dolphin social network, Proceedings of the Royal Society B Biological Sciences270(Suppl 2) (2003), S186–S188.
26.
NewmanM.E.J., Modularity and community structure in networks, Proceedings of the National Academy of Sciences103(23) (2006), 8577–8582.
27.
ZakiN.BerengueresJ. and EfimovD., ProRank: a method for detecting protein complexes, in: Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation, 2012, pp. 209–216.
28.
YuH.BraunP.YldrmM.A. et al., High-quality binary protein interaction map of the yeast interactome network, Science322(5898) (2008), 104–110.
29.
GleiserP.M. and DanonL., Community structure in jazz, Advances in Complex Systems6(4) (2003), 565–573.
30.
GongM.CaiQ.ChenX. et al., Complex network clustering by multiobjective discrete particle swarm optimization based on decomposition, IEEE Transactions on Evolutionary Computation18(1) (2013), 82–97.
31.
HanJ.D.J.DupuyD.BertinN. et al., Effect of sampling on topology predictions of protein-protein interaction networks, Nature Biotechnology23(7) (2005), 839–844.
32.
CusickM.E.YuH.SmolyarA. et al., Literature-curated protein interaction datasets, Nature Methods6(1) (2009), 39.
33.
WattsD.J. and StrogatzS.H., Collective dynamics of small-worldnetworks, Nature393(6684) (1998), 440.
34.
GregoryS., Finding overlapping communities in networks by label propagation, New Journal of Physics12(10) (2010), 103018.
35.
NicosiaV.MangioniG.CarchioloV. et al., Extending the definition of modularity to directed graphs with overlapping communities, Journal of Statistical Mechanics: Theory and Experiment2009(3) (2009), P03024.
