Top

Journal of Intelligent Information Systems

Published in:

17-08-2017

Evaluation of local community metrics: from an experimental perspective

Authors: Lianhang Ma, Kevin Chiew, Hao Huang, Qinming He

Published in: Journal of Intelligent Information Systems | Issue 1/2018

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Local community detection (LCD for short) aims at finding a community structure in a network starting from a seed (i.e., a “local” starting vertex). In a process of LCD, local community metrics are crucial since they serve as the measurements for the quality of the detected local community. Even if various algorithms have been proposed for LCD, there has been few investigation on the key features of these local community metrics, resulting in a lack of guidelines on how to choose these metrics in practice. To make up this inadequacy, this paper first investigates the effectiveness and efficiency of local community metrics via LCD accuracy comparison and scalability study, and then studies the insensitivity of these metrics to different seeds in a target community structure, followed by evaluating their performance on local communities with noisy vertices inside. In addition, a set of guidelines for the selection of local community metrics are given based on our findings concluded from extensive experiments.

next article A hybrid approach for measuring semantic similarity based on IC-weighted path distance in WordNet

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

http://snap.stanford.edu/

Ahn, Y.Y., Bagrow, J.P., & Lehmann, S. (2010). Link communities reveal multi-scale complexity in networks. Nature, 466, 761–764.CrossRef

Bagrow, J.P. (2008). Evaluating local community methods in networks. Journal of Statistical Mechanics-Theory and Experiment, 5, P05,001.

Bagrow, J.P., & Bollt, E.M. (2005). Local method for detecting communities. Physical Review E, 72(4), 046–108.CrossRef

Blondel, V.D., Guillaume, J.L., Lambiotte, R., & Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of Statistical Mechanics-Theory and Experiment, P10008.

Chen, J., Zaïane, O.R., & Goebel, R. (2009). Detecting communities in social networks using max-min modularity, SDM (pp. 978–989).

Chen, J., Zaïane, O.R., & Goebel, R. (2009). Local community identification in social networks, ASNAM (pp. 237–242).

Ciglan, M., Laclavik, M., & Nørvåg, K. (2013). On community detection in real-world networks and the importance of degree assortativity, KDD (pp. 1007–1015).

Clauset, A. (2005). Finding local community structure in networks. Physical Review E, 72(2), 026,132.CrossRef

Coscia, M., Rossetti, G., Giannotti, F., & Pedreschi, D. (2012). Demon: a local-first discovery method for overlapping communities, KDD (pp. 615–623).

Cui, W., Xiao, Y., Wang, H., & Wang, W. (2014). Local search of communities in large graphs, SIGMOD (pp. 991–1002).

Duch, J., & Arenas, A. (2005). Community detection in complex networks using extremal optimization. Physical Review E 72(2).

Fortunato, S. (2010). Community detection in graphs. Physics Reports, 486(3–5), 75–174.MathSciNetCrossRef

Fortunato, S., & Barthelemy, M. (2007). Resolution limit in community detection. Proceedings of the National Academy of Sciences, 104(1), 36–41.CrossRef

Girvan, M., & Newman, M.E.J. (2002). Community structure in social and biological networks. Proceedings of the National Academy of Sciences, 99(12), 7821–7826.MathSciNetCrossRefMATH

Gleich, D.F., & Seshadhri, C. (2012). Vertex neighborhoods, low conductance cuts, and good seeds for local community methods, KDD (pp. 597–605).

Huang, H., Chiew, K., Gao, Y., He, Q., & Li, Q. (2014). Rare category exploration. Expert Systems with Applications, 41(9), 4197–4210.CrossRef

Huang, H., Gao, Y., Chiew, K., He, Q., & Zheng, B. (2014). Unsupervised analysis of top-k core members in poly-relational networks. Expert Systems with Applications, 41(13), 5689–5710.CrossRef

Huang, J., Sun, H., Han, J., Deng, H., Sun, Y., & Liu, Y. (2010). Shrink: a structural clustering algorithm for detecting hierarchical communities in networks, CIKM (pp. 219–228).

Huang, J., Sun, H., Liu, Y., Song, Q., & Weninger, T. (2011). Towards online multiresolution community detection in large-scale networks. PLOS ONE, 6(8), e23–829.CrossRef

Lancichinetti, A., & Fortunato, S. (2009). Community detection algorithms: a comparative analysis. Physical Review E, 80(5), 056–117.CrossRef

Lancichinetti, A., Fortunato, S., & Kertesz, J. (2009). Detecting the overlapping and hierarchical community structure in complex networks. New Journal of Physics, 11 (033), 015.

Leskovec, J., Kleinberg, J.M., & Faloutsos, C. (2007). Graph evolution: densification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data 1(1).

Leskovec, J., Lang, K.J., & Mahoney, M.W. (2010). Empirical comparison of algorithms for network community detection, WWW (pp. 631–640).

Luo, F., Wang, J.Z., & Promislow, E. (2006). Exploring local community structures in large networks, WI (pp. 233–239).

Ma, L., Huang, H., He, Q., Chiew, K., Wu, J., & Che, Y. (2013). GMAC: a seed-insensitive approach to local community detection, Dawak (pp. 297–308).

Ma, L., Huang, H., He, Q., Chiew, K., & Liu, Z. (2014). Toward seed-insensitive solutions to local community detection. Journal of Intelligent Information Systems, 43 (1), 183–203.CrossRef

Newman, M.E.J., & Girvan, M. (2004). Finding and evaluating community structure in networks. Physical Review E 69(2).

Shi, J., & Malik, J. (2000). Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8), 888–905.CrossRef

Shibata, N., Kajikawa, Y., Takeda, Y., Sakata, I., & Matsushima, K. (2011). Detecting emerging research fronts in regenerative medicine by the citation network analysis of scientific publications. Technological Forecasting and Social Change, 78(2), 274–282.CrossRef

Sun, H., Huang, J., Han, J., Deng, H., Zhao, P., & Feng, B. (2010). Gskeletonclu: density-based network clustering via structure-connected tree division or agglomeration, ICDM (pp. 481–490).

Wang, G., Zhao, Y., Shi, X., & Yu, P.S. (2012). Magnet community identification on social networks, KDD (pp. 588–596).

Watts, D.J., & Strogatz, S.H. (1998). Collective dynamics of small-world networks. Nature, 393(6684), 440–442.CrossRefMATH

Yang, J., & Leskovec, J. (2012). Defining and evaluating network communities based on ground-truth, ICDM (pp. 745–754).

Zhang, W., Pan, G., Wu, Z., & Li, S. (2013). Online community detection for large complex networks, IJCAI (pp. 1903–1909).

Title: Evaluation of local community metrics: from an experimental perspective
Authors: Lianhang Ma
Kevin Chiew
Hao Huang
Qinming He
Publication date: 17-08-2017
Publisher: Springer US
Published in: Journal of Intelligent Information Systems / Issue 1/2018
Print ISSN: 0925-9902
Electronic ISSN: 1573-7675
DOI: https://doi.org/10.1007/s10844-017-0480-5

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 1/2018

Topic detection and tracking on heterogeneous information

Toward analyzing impact of disjoint axioms for merging heterogeneous ontologies

A survey of book recommender systems

Anytime diagnosis for reconfiguration

Predicting the popularity of topics based on user sentiment in microblogging websites

Recommendation using a clustering algorithm based on a hybrid features selection method

Premium Partner