Generic placeholder image

Recent Advances in Computer Science and Communications

Author(s): Smita Agrawal* and Atul Patel

DOI: 10.2174/2213275912666190710183635

DownloadDownload PDF Flyer Cite As
Clustering Algorithm for Community Detection in Complex Network: A Comprehensive Review

Page: [542 - 549] Pages: 8

  • * (Excluding Mailing and Handling)

Explore Articles
About Journal
For Authors
For Editors
For Reviewers

Abstract

Many real-world social networks exist in the form of a complex network, which includes very large scale networks with structured or unstructured data and a set of graphs. This complex network is available in the form of brain graph, protein structure, food web, transportation system, World Wide Web, and these networks are sparsely connected, and most of the subgraphs are densely connected. Due to the scaling of large scale graphs, efficient way for graph generation, complexity, the dynamic nature of graphs, and community detection are challenging tasks. From large scale graph to find the densely connected subgraph from the complex network, various community detection algorithms using clustering techniques are discussed here. In this paper, we discussed the taxonomy of various community detection algorithms like Structural Clustering Algorithm for Networks (SCAN), Structural-Attribute based Cluster (SA-cluster), Community Detection based on Hierarchical Clustering (CDHC), etc. In this comprehensive review, we provide a classification of community detection algorithm based on their approach, dataset used for the existing algorithm for experimental study and measure to evaluate them. In the end, insights into the future scope and research opportunities for community detection are discussed.

Keywords: Graph clustering, community detection, complex network, collaborative similarity, vertex similarity, data set of community detections.

Graphical Abstract

[1]
M. Dehmer , F. Emmert-Streib , S. Pickl , and A. Holzinger . Big Data of Complex Networks Chapman & Hall/CRC London, United Kingdom. 2016.
[2]
Y. Wang , L.A. Kung , and T.A. Byrd . "Big data analytics: Understanding its capabilities and potential benefits for healthcare organizations". Technol Forecast Soc Change vol. 126, pp. 3-13, 2018
[http://dx.doi.org/10.1016/j.techfore.2015.12.019]
[3]
J.O. Garcia , A. Ashourvan , S.F. Muldoon , J.M. Vettel , and D.S. Bassett . "Applications of community detection techniques to brain graphs: Algorithmic considerations and implications for neural function" Proc IEEE Inst Electr Electron Eng. vol. 106 no. 5, pp.: 846-67. 2018
[http://dx.doi.org/10.1109/JPROC.2017.2786710] [PMID: 30559531]
[4]
J. Han , M. Kamber , and J. Pei . "Chapter 9: Graph Mining, Social Network Analysis, and Multirelational Data Mining" Data Min concepts Tech, pp 535-589,. 2006.
[5]
E. Society , and E. Monographs . The Seasonal Dynamics of The Chesapeake Bay Ecosystem Author ( s ): Daniel Baird and Robert E . Ulanowicz Published by : Wiley on behalf of the Ecological Society of America Stable URL., vol. 59, 2019no. 4, pp. 329-364 https://www.jstor.org/stable/1943071
[6]
J. Celko . Graph Databases 2014.
[http://dx.doi.org/10.1016/B978-0-12-407192-6.00003-0]
[7]
S. Brin , and L. Page . The anatomy of a large scale hypertextual Web search engine 1998.
[http://dx.doi.org/10.1016/S0169-7552(98)00110-X]
[8]
T. Suel , and J.Y.J. Yuan . "Compressing the graph structure of the Web Data Compression Conf". 2001; pp. 1-10.
[http://dx.doi.org/10.1109/DCC.2001.917152]
[9]
K. Desai , V. Devulapalli , S. Agrawal , P. Kathiria , and A. Patel . "Web Crawler: Review of Different Types of Web Crawler, Its Issues, Applications and Research Opportunities". Int J Adv Res Comput Sci , vol. 8, no. 3,: 1199-202. 2017
[10]
W. Local . (12) Patent Application Publication (10) Pub . No .: US 2006 / 0190419 A1, vol. 1, no. 19 2006.
[11]
S. Agrawal , and A. Patel . Essentials of NoSQL Database in building applications based on Internet of Things (IoT), vol. 10, no. 6, 1829 1837. 2017
[12]
C. Giatsidis , F.D. Malliaros , and M. Vazirgiannis . "Advanced graph mining for community evaluation in social networks and the web" In: Proc sixth ACM Int Conf Web search data Min - WSDM vol 13. 2013; p. 71.
[http://dx.doi.org/10.1145/2433396.2433495]
[13]
H. Mahmoud , F. Masulli , S. Rovetta , and G. Russo . "Community detection in protein-protein interaction networks using spectral and graph approaches" In: International Meeting on Computational Intelligence Methods for Bioinformatics and Biostatistics. 2013; pp. 62-75.
[14]
N. Du , B. Wang , and B. Wu . Community Detection in Large-Scale Social Networks 16-25.
[http://dx.doi.org/10.1145/1348549.1348552]
[15]
J. Scott . Social network analysis. Sage 2017.
[16]
S. Wasserman , and K. Faust . Social network analysis: Methods and applications Vol 8. Cambridge university press 1994.
[http://dx.doi.org/10.1017/CBO9780511815478]
[17]
E. Baatarjav , S. Phithakkitnukoon , and R. Dantu . Group Recommendation System for Facebook 2008; 211-9.
[18]
X. Xu , and T.A.J. Schweiger . SCAN : A Structural Clustering Algorithm for Networks. 2007; pp. 824-33.
[http://dx.doi.org/10.1145/1281192.1281280]
[19]
C. Yin , S. Zhu , H. Chen , B. Zhang , and B. David . A Method for Community Detection of Complex Networks Based on Hierarchical Clustering vol. 2015; 2015.
[20]
M.J. Rattigan , M. Maier , and D. Jensen . "Graph clustering with network structure indices" Int Conf Mach Learn vol. vol. CI, 2007pp. 783-790
[21]
M.E.J. Newman . Modularity and community structure in networks Vol 103, no 23, pp 8577-8582, 20062006
[http://dx.doi.org/10.1073/pnas.0601602103]
[22]
P. Pons , and M. Latapy . Computing Communities in Large Networks Using Random Walks vol. 10, no. 2,: 191-218. 2006
[23]
J. Denise , J. Denise , L. Yen , D. Vanvyve , and F. Wouters . Clustering using a random walk-based distance measure " Référence bibliographique Clustering using a random walk based distance measure", 2005; 317-24.
[24]
Y. Zhou , H. Cheng , and J.X. Yu . "Graph Clustering Based on Structural/Attribute Similarities". Vldb Vol. 2, no. 1,: 718-29. 2009
[http://dx.doi.org/10.14778/1687627.1687709]
[25]
H.F. Zhou , J. Li , J.H. Li , F.C. Zhang , and Y.A. Cui . "A graph clustering method for community detection in complex networks", Phys. A Stat. Mech Its Appl Vol. 469: 551-62.2017;
[http://dx.doi.org/10.1016/j.physa.2016.11.015]
[26]
W. Nawaz , K. Khan , and S. Lee . Intra graph clustering using collaborative similarity measure Intra Graph Clustering using Collaborative Similarity 2015.
[27]
M. Ganji . Semi-supervised Community Detection and Clustering Mohadeseh. 2017; pp. 655-70.
[28]
Agrawal SS, Patel A . CSG cluster: A collaborative similarity based graph clustering for community detection in complex networks (2019) International Journal of Engineering and Advanced Technology, . (5)1682-7. Scopus link: https://www.sco pus.com/record/display.uri?eid=2-s2.0-85070000801&origin=inward&txGid=ad4558f236c2055ea97dd066c84c6390
[29]
C. Bothorel , J. D. Cruz , and M. Magnani . arXiv : 1501. 01676v1 [ cs. SI ] 7 Jan 2015 Clustering attributed graphs : models, measures and methods 2015.
[30]
X. Li , M.K. Ng , and Y. Ye . "MultiComm : Finding Community Structure in Multi-Dimensional Networks". IEEE Trans Knowl Data Eng vol. 26, no. 4: 929-41.2014;
[http://dx.doi.org/10.1109/TKDE.2013.48]
[31]
Y. Zhou , H. Cheng , and J.X. Yu . "Clustering large attributed graphs: An efficient incremental approach Proc. - IEEE Int. Conf. Data Mining, ICDM" 689-98. 2010
[http://dx.doi.org/10.1109/ICDM.2010.41]
[32]
M. Chen , S. Mao , and Y. Liu . "Big data: A survey". Mob Netw Appl vol. 19, no. 2, : 171-209.2014;
[http://dx.doi.org/10.1007/s11036-013-0489-0]
[33]
K. Rohloff , and R.E. Schantz . “"Clause-iteration with MapReduce to Scalably Query Datagraphs in the SHARD Graph-store,” Proc. Fourth Int. Work. Data-intensive." Distrib Comput pp. 35-44, 2011;
[34]
Y. Low , D. Bickson , J. Gonzalez , C. Guestrin , A.Kyrola , and J.M. Hellerstein . "Distributed GraphLab" Proc VLDB Endow vol. 5, no. 8,: 716-27.2012;
[http://dx.doi.org/10.14778/2212351.2212354]
[35]
A. Katal , M. Wazid , and R.H. Goudar . "Big data: Issues, challenges, tools and Good practices". Conf Contemp Comput IC32013; : 404-9.
[http://dx.doi.org/10.1109/IC3.2013.6612229]
[36]
J. Lai . Implementations of iterative algorithms in Hadoop and Spark by 2014.
[37]
E. Carlini , P. Dazzi , A. Esposito , A. Lulli , and L. Ricci . “Balanced Graph Partitioning with Apache Spark,” Euro-Par 2014 Parallel Process". Work no. 8805: 129-40. 2014
[38]
D. Lasalle , and G. Karypis . "MPI for Big Data: New tricks for an old dog". Parallel Comput vol. 40, no. 10, pp. 754-767 2014
[http://dx.doi.org/10.1016/j.parco.2014.07.003]
[39]
G. Oyarzun , R. Borrell , A. Gorobets , and A. Oliva . "MPI-CUDA sparse matrix-vector multiplication for the conjugate gradient method with an approximate inverse preconditioner". Comput Fluids vol. 92, pp: 244-52. 2014
[http://dx.doi.org/10.1016/j.compfluid.2013.10.035]
[40]
P. S. Agrawal , P. P. Kathiria , A. Patel , and G. Aswani . Performance evaluation of counting words from files using OpenMP
[41]
R. A. Rossi , R. Zhou , and N. K. Ahmed . Deep Feature Learning for Graphs pp. 1-11.
[42]
J. You , R. Ying , X. Ren , W. L. Hamilton , and J. Leskovec . GraphRNN : Generating Realistic Graphs with Deep Auto-regressive Models 2018.
[43]
A. Mohammadzadeh , and W. Zhang . "Dynamic programming strategy based on a type-2 fuzzy wavelet neural network". Nonlinear Dyn 2018.
[44]
A. Mohammadzadeh , and E. Kayacan . "A non-singleton type-2 fuzzy neural network with adaptive secondary membership for high dimensional applications". Neurocomputing vol. 338, pp: 63-71. 2019
[http://dx.doi.org/10.1016/j.neucom.2019.01.095]
[45]
J.P. Verma , S. Agrawal , B. Patel , and A. Patel . "Big Data Analytics: Challenges and Applications for Text, Audio, Video, and Social media Data". Int J Soft Comput Artif Intell Appl vol. 5, no. 1, pp: 41-51. 2016
[http://dx.doi.org/10.5121/ijscai.2016.5105]
[46]
S. Agrawal , and A. Patel . "a Study on Graph Storage Database of Nosql". Int J Soft Comput Artif Intell Appl vol. 5, no. 1, pp. 33-39 2016
[http://dx.doi.org/10.5121/ijscai.2016.5104]
[47]
S. Yadav , J. Verma , and S. Agrawal . "SUTRON: IoT-based Industrial/Home Security and Automation System to Compete the Smarter World". Int J Appl Res Inf Technol Comput vol. 8, no. 2, pp. 193-198, 2017
[http://dx.doi.org/10.5958/0975-8089.2017.00016.1]
[48]
T. Wang . "Inter-Community Detection Scheme for Social Internet of Things: A Compressive Sensing Over Graphs Approach" IEEE Internet Things J vol. 4662, 2018.
[49]
C. Shi . IN LARGE-SCALE COMPLEX NETWORKS vol. 13, no. 1, pp. 3-17, 2010.
[50]
C. Pizzuti . GA-Net : A Genetic Algorithm for Community Detection in Social Networks GA-Net : A Genetic Algorithm for Community Detection in Social Networks 2014.
[51]
R. Shang , J. Bai , L. Jiao , and C. Jin . "Community detection based on modularity and an improved genetic algorithm." Physica A vol. 392, no. 5, pp. 1215-1231, 2013
[http://dx.doi.org/10.1016/j.physa.2012.11.003]
[52]
J. Wu , Y. Hou , Y. Jiao , Y. Li , X. Li , and L. Jiao . "Density shrinking algorithm for community detection with path based similarity" Phys A Stat Mech its Appl vol. 433, pp. 218-228, 2015.
[http://dx.doi.org/10.1016/j.physa.2015.03.044]
[53]
X. Zhou , Y. Liu , J. Wang , and C. Li . "A density based link clustering algorithm for overlapping community detection in networks" Phys A Stat Mech its Appl vol. 486, pp. 65-78, 2017.
[http://dx.doi.org/10.1016/j.physa.2017.05.032]
[54]
M. Li , and J. Liu . A link clustering based memetic algorithm for overlapping community detection 2018.
[http://dx.doi.org/10.1016/j.physa.2018.02.133]
[55]
W.W. Zachary . "An information flow model for conflict and fission in small groups". J Anthropol Res vol. 33, no. 4, pp. 452-473, 1977
[http://dx.doi.org/10.1086/jar.33.4.3629752]
[56]
L.A. Adamic , and N. Glance . "The political blogosphere and the 2004 US election: divided they blog" Proceedings of the 3rd international workshop on Link discovery 2005pp. 36-43
[http://dx.doi.org/10.1145/1134271.1134277]
[57]
D. Lusseau , K. Schneider , O.J. Boisseau , P. Haase , E. Slooten , and S.M. Dawson . "The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations". Behav Ecol Sociobiol vol. 54, no. 4, pp 396-405, 2003.
[http://dx.doi.org/10.1007/s00265-003-0651-y]
[58]
M.E.J. Newman , and M. Girvan . "Finding and evaluating community structure in networks Phys Rev E Stat Nonlin Soft Matter Phys". vol. 69, no. 2 Pt 2, 2004.026113
[http://dx.doi.org/10.1103/PhysRevE.69.026113] [PMID: 14995526]
[59]
J. Yang , and J. Leskovec . "Defining and evaluating network communities based on ground-truth". Knowl Inf Syst vol. 42, no. 1, pp. 181-213, 2015
[http://dx.doi.org/10.1007/s10115-013-0693-z]
[60]
"Internet movie Database",
[http://dx.doi.org/10.1007/s10115-013-0693-z]
[61]
P. Sen , G. Namata , M. Bilgic , L. Getoor , B. Galligher , and T. Eliassi-Rad . "Collective classification in network data". AI Mag vol. 29, no. 3, p. 93, 2008
[http://dx.doi.org/10.1609/aimag.v29i3.2157]
[62]
V. Krebs . Books on us politics unpublished