Methods for detecting overlapping communities are essential for understanding complex network structures and extracting implied information. Traditional community detection algorithms have been proven to be unsatisfactory when the network community structure is relatively fuzzy. In this paper, we proposed a novel overlapping community discovery algorithm (ENFI) to address this problem on the micro level using ego-nets. The ENFI approach exploits the micro-characteristics of ego-nets, extracts the ego-net’s local community by calculating the friend intimacy, and then forms the overlapping communities of the network. We conducted experiments on both synthetic and real-world social networks using normalized mutual information (NMI) and overlapping community modularity as evaluation criteria. The results demonstrated that the proposed ENFI algorithm can detect community structures in complex networks more efficiently and accurately than existing state-of-the-art algorithms.
PallaG., DerenyiI., Farkas and VicsekT., Uncovering the overlapping community structure of complex networks in nature and society, in: Nature435 (2005), 814–818.
2.
GregoryS., Finding overlapping communities in networks by label propagation, in: New Journal of Physics12 (2010), 103018.
3.
LeeC., ReidF., McDaidA., HurleyN., Detecting highly overlapping community structure by greedy clique expansion, in: The 4th SNA-KDD Workshop, USA, 2010.
4.
LeskovecJ., LandK.J., DasguptaA., MahoneyM.W., Community structure in large networks, Nature cluster sizes and the absence of large well-defined clusters, in: Internet Mathematics, 2009.
5.
AbrahaoB.D., SoundarajanS., HopcroftJ.E., KleinbergR.D., A separability framework for analyzing community structure, in: TKDD, 2014.
6.
CosciaM., RosettiG., GiannottiF., PedreschiD., Uncovering hierarchical and overlapping communities with a local-first approach, in: TKDD, 2014.
7.
FreemanL.C., Centered graphs and the structure of ego networks, in: Mathematical Social Sciences3 (2005), 291–304.
8.
EverettM., BorgattiS.P., Ego network betweenness, in: Social Networks27 (2005), 31–38.
9.
GuptaS., YanX., LermanK., Structural Properties of Ego Networks, in: International Conference on Social Computing, Behavioral-Cultural Modeling, and Prediction, 2015, pp. 55–64.
10.
BurtP., Structureal Holes: The Social Structure of Competition, in: Harvard University Press, 1995.
11.
DunbarR.I.M., RobertsS.G.B., Communication in social networks: Effects of kinship, network size and emotional closeness, in: Personal Relationships, 2010.
12.
EverettM., BorgattiS.P., Ego network betweenness, in: Social Networks27 (2005), 31–38.
13.
WassermanS., FausK., Social Network analysis: methods and applications, in: Social Network Analysis: Methods and Applications, 1994.
14.
ReeB.S., GallagherK.B., Overlapping community detection by collective friend-ship group inference, in: ASONAM, 2010.
15.
CosciaM., RossettiG., GiannottiF., PedreschiD., Uncovering hierarchical and overlapping communities with a local first approach, in: TKDD, 2014.
16.
BuzunN., KorshunovA., AvanesovV., FilonenkoI., KozlovI., TurdakovD., KimH., EgoLP: Fast and Distributed community detection in billion-node social networks, in: In 2014 IEEE ICDM Workshops, 2014, 533–540.
17.
DelisA., NtoulasA., LiakosP., Scalable link community detection: A local dispersion aware approach, in: In IEEE Big Data, 2016, pp. 716–725.
18.
EpastoA., LattanziS., LemeR.P., Ego-splitting framework: From non-overlapping to overlapping clusters, in: In Proceedings of ACM SIGKDD Conference on Knowledge Discovery and Data Mining KDD(KDD’17), 2017.
19.
McAuleyJ.J., LeskovecJ., Learning to discover social circles in ego networks, in: NIPS, 2012.
20.
ChengX.Q., GuoJ.F., ShenH.W., Quantifying and identifying the overlapping community structure in networks, in: Journal of Statistical Mechanics Theory & Experiment7 (2012), pp. 07042.
21.
NicosiaV., MangioniG., CarchioloV., MalgeriM., Extending the definition of modularity to directed graphs with overlapping communities, in: Journal of Statistical Mechanics Theory and Experiment3 (2009), 3166–3168.
22.
LancichinettiA., FortunatoS., Community detection algorithms: A comparative analysis, in: Phys Rev E80 (2009), 056117.
23.
LancichinettiA., FortunatoS., KerteszJ., Detecting the overlapping and hierarchical community structure of complex networks, in: New J Phys11 (2009), 033015.
24.
XieJ., SzymanskiB.K., LiuX., SLPA: Uncovering overlapping communities in social networks via a speaker-listener interation dynamic process, in: Proceedings ICDM Workshop, 2011, 344–349.
25.
GregoryS., Finding overlapping communities in networks by label propagation, in: New Journal of Physics12 (2010), 103018.
26.
BrutzM., MeyerF.G., A flexible multiscale approach to overlapping community detection, in: Social Network Analysis and Mining5 (2015), 23.
27.
LancichinettiA., FortunatoS., Community detection algorithms: A comparative analysis, in: Phys Rev E12 (2009), 056117.
28.
FreemanL.C.T., Centered graphs and the structure of ego networks, in: Mathematical Social Sciences (1982).
29.
WangY., GaoL., An edge-based clustering algorithm to detect social cir-cles in ego networks, in: New Journal of Physics8 (2013), 2575–2582.
30.
BiswasA., BiswasB., Analyzing evolutionary optimization and community de-tection algorithms using regression line dominance, in: Information Sciences369 (2017), 2575–2582.
31.
LiuW., JiangX., PellegriniM., et al., Discovering communities in complex networks by edge label propagation, in: Sci Rep12 (2010), 103018.
32.
SheikholeslamiF., BainganaB., GiannakisG.B., et al., Egonet tensor decomposition for community identifica-tion, Signal and Information Processing, 2017, 341–345.
33.
McauleyJ., LeskovecJ., Discovering social circles in ego networks, in: Acm Transactions on Knowledge Discovery from Data8 (2012), 1–28.
34.
BaiX., YangP., ShiX., An overlapping community detection algorithm based on density peaks, in: Neuro Computing226 (2017), 7–15.
35.
ZouF., ChenD., LiS., et al., Community detection in complex networks: Multi-objective discrete backtracking search optimization algorithm with decomposition, in: Applied Soft Computing53 (2017), 285–295.
