International Journal of Advanced Networking and Applications

Open Access Open Access  Restricted Access Subscription Access

A Proposed Algorithm to Detect the Largest Community Based On Depth Level (LC-BDL)


Affiliations
1 Canadian International College, Cairo, Egypt
2 Helwan University, Cairo, Egypt
 

The incredible rising of online networks show that these networks are complex and involving massive data.Giving a very strong interest to set of techniques developed for mining these networks. The clique problem is a well known NP-Hard problem in graph mining. One of the fundamental applications for it is the community detection. It helps to understand and model the network structure which has been a fundamental problem in several fields. In literature, the exponentially increasing computation time of this problem make the quality of these solutions is limited and infeasible for massive graphs. Furthermore, most of the proposed approaches are able to detect only disjoint communities. In this paper, we present a new clique based approach for fast and efficient overlapping community detection. The work overcomes the shortfalls of clique percolation method (CPM), one of most popular and commonly used methods in this area. The shortfalls occur due to brute force algorithm for enumerating maximal cliques and also the missing out many vertices thatleads to poor node coverage. The proposed work overcome these shortfalls producing NMC method for enumerating maximal cliques then detects overlapping communities using three different community scales based on three different depth levels to assure high nodes coverage and detects the largest communities. The clustering coefficient and cluster density are used to measure the quality. The work also provide experimental results on benchmark real-world network to demonstrate the efficiency and compare the new proposed algorithm with CPM method, The proposed algorithm is able to quickly discover the maximal cliques and detects overlapping community with interesting remarks and findings.

Keywords

Graph Mining, Maximal Clique Problem, Overlapping Community Detection, Social Network Analysis.
User
Notifications
Font Size

  • Bedi, Punam, and Chhavi Sharma. "Community detection in social networks."Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery 6.3 (2016): 115-135.

  • Cuvelier, Etienne, and Marie-AudeAufaure. "Graph mining and communities detection." Business Intelligence.Springer Berlin Heidelberg, 2012.117138.

  • Adedoyin-Olowe, Mariam, Mohamed MedhatGaber, and Frederic Stahl. "A survey of data mining techniques for social media analysis." arXiv preprint arXiv:1312.4617 (2013).

  • Afsarmanesh, Nazanin, and MatteoMagnani. "Finding overlapping communities in multiplex networks." arXiv preprint arXiv:1602.03746 (2016).

  • Zafarani, Reza, Mohammad Ali Abbasi, and Huan Liu. Social media mining: an introduction. Cambridge University Press, 2014.

  • McCreesh, Ciaran, et al. "Clique and constraint models for maximum common (connected) subgraph problems." International Conference on Principles and Practice of Constraint Programming.Springer International Publishing, 2016.

  • Reid, Fergal, Aaron McDaid, and Neil Hurley. "Percolation computation in complex networks." Advances in Social Networks Analysis and Mining (ASONAM), 2012 IEEE/ACM International Conference on. IEEE, 2012.

  • Palla, Gergely, et al. "k-clique Percolation and Clustering." Handbook of Large-Scale Random Networks.Springer Berlin Heidelberg, 2008.369-408.

  • Wang, Jianxin, et al. "Identifying protein complexes from interaction networks based on clique percolation and distance restriction." BMC genomics 11.2 (2010): S10.

  • McDaid, Aaron, and Neil Hurley. "Detecting highly overlapping communities with model-based overlapping seed expansion." Advances in Social Networks Analysis and Mining (ASONAM), 2010 International Conference on. IEEE, 2010.

  • Zachary, Wayne W. "An information flow model for conflict and fission in small groups." Journal of anthropological research 33.4 (1977): 452-473.

  • Palla, Gergely, et al. "Uncovering the overlapping community structure of complex networks in nature and society." arXiv preprint physics/0506133 (2005).

  • Nandi, G., and A. Das. "A survey on using data mining techniques for online social network analysis." Int. J. Comput. Sci. Issues (IJCSI) 10.6 (2013): 162-167.

  • Pattabiraman, Bharath, et al. "Fast Algorithms for the Maximum Clique Problem on Massive Sparse Graphs." WAW. 2013.

  • Palsetia, Diana, et al. "Clique guided community detection." Big Data (Big Data), 2014 IEEE International Conference on.IEEE, 2014.

  • Leskovec, Jure, Kevin J. Lang, and Michael Mahoney. "Empirical comparison of algorithms for network community detection." Proceedings of the 19th international conference on World wide web. ACM, 2010.

  • Yang, Jaewon, Julian McAuley, and Jure Leskovec. "Community detection in networks with node attributes." Data Mining (ICDM), 2013 IEEE 13th international conference on.IEEE, 2013.

  • Harenberg, Steve, et al. "Community detection in large‐scale networks: a survey and empirical evaluation." Wiley Interdisciplinary Reviews: Computational Statistics 6.6 (2014): 426-439.

  • Lancichinetti, Andrea, Santo Fortunato, and JánosKertész. "Detecting the overlapping and hierarchical community structure in complex networks." New Journal of Physics 11.3 (2009): 033015.

  • Du, Nan, et al. "Community detection in large-scale social networks." Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 workshop on Web mining and social network analysis.ACM, 2007.

  • Shen, Huawei, et al. "Detect overlapping and hierarchical community structure in networks." Physica A: Statistical Mechanics and its Applications 388.8 (2009): 1706-1712.

  • Evans, T. S., and Renaud Lambiotte. "Line graphs, link partitions, and overlapping communities." Physical Review E 80.1 (2009): 016105.

  • Evans, Tim S., and Renaud Lambiotte. "Line graphs of weighted networks for overlapping communities." The European Physical Journal BCondensed Matter and Complex Systems 77.2 (2010): 265-272.

  • Evans, Tim S. "Clique graphs and overlapping communities." Journal of Statistical Mechanics: Theory and Experiment 2010.12 (2010): P12037.

  • Lee, Conrad, et al. "Detecting highly overlapping community structure by greedy clique expansion." arXiv preprint arXiv:1002.1827 (2010).

  • Gregory, Steve. "A fast algorithm to find overlapping communities in networks." Machine learning and knowledge discovery in databases (2008): 408-423.

  • Gregory, Steve. "Finding overlapping communities using disjoint community detection algorithms." Complex networks (2009): 47-61.

  • Adamcsek, Balázs, et al. "CFinder: locating cliques and overlapping modules in biological networks." Bioinformatics 22.8 (2006): 1021-10


Abstract Views: 312

PDF Views: 0




  • A Proposed Algorithm to Detect the Largest Community Based On Depth Level (LC-BDL)

Abstract Views: 312  |  PDF Views: 0

Authors

Mohamed H. Farrag
Canadian International College, Cairo, Egypt
Mona M. Nasr
Helwan University, Cairo, Egypt

Abstract


The incredible rising of online networks show that these networks are complex and involving massive data.Giving a very strong interest to set of techniques developed for mining these networks. The clique problem is a well known NP-Hard problem in graph mining. One of the fundamental applications for it is the community detection. It helps to understand and model the network structure which has been a fundamental problem in several fields. In literature, the exponentially increasing computation time of this problem make the quality of these solutions is limited and infeasible for massive graphs. Furthermore, most of the proposed approaches are able to detect only disjoint communities. In this paper, we present a new clique based approach for fast and efficient overlapping community detection. The work overcomes the shortfalls of clique percolation method (CPM), one of most popular and commonly used methods in this area. The shortfalls occur due to brute force algorithm for enumerating maximal cliques and also the missing out many vertices thatleads to poor node coverage. The proposed work overcome these shortfalls producing NMC method for enumerating maximal cliques then detects overlapping communities using three different community scales based on three different depth levels to assure high nodes coverage and detects the largest communities. The clustering coefficient and cluster density are used to measure the quality. The work also provide experimental results on benchmark real-world network to demonstrate the efficiency and compare the new proposed algorithm with CPM method, The proposed algorithm is able to quickly discover the maximal cliques and detects overlapping community with interesting remarks and findings.

Keywords


Graph Mining, Maximal Clique Problem, Overlapping Community Detection, Social Network Analysis.

References