Top

Journal of Intelligent Information Systems

Published in:

01-08-2014

Toward seed-insensitive solutions to local community detection

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

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

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

search-config

AI-assisted search

Off

Abstract

Local community detection aims at finding a community structure starting from a seed which is a given vertex in a network without global information, such as online social networks that are too large and dynamic to ever be known fully. Nonetheless, the existing approaches to local community detection are usually sensitive to seeds, i.e., some seeds may lead to missing of some true communities. In this paper, we present a seed-insensitive method called GMAC and its variation iGMAC for local community detection. They estimate the similarity among vertices by investigating vertices’ neighborhoods, and reveal a local community by maximizing its internal similarity and minimizing its external similarity simultaneously. Extensive experimental results on both synthetic and real-world data sets verify the effectiveness of our algorithms.

previous article Algorithms for spatial collocation pattern mining in a limited memory environment: a summary of results

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

A conference version of GMAC can be found in (Ma et al. 2013).

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

Bagrow, J. P., & Bollt, E. M. (2005). Local method for detecting communities. Physical Review E, 72(4), 046108.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.

Branting, K. (2010). Incremental detection of local community structure. In Proceedings of international conference on advances in social networks analysis and mining, Odense, Denmark, August 9–11, 2010 (pp. 80–87).

Chen, H.-H., Gou, L., Zhang, X. L., Giles, C. L. (2012). Discovering missing links in networks using vertex similarity measures. In Proceedings of the ACM symposium on applied computing, Riva, Trento, Italy, March, 26–30, 2012 (pp. 138–143).

Chen, J., Zaïane, O. R., Goebel, R. (2009a). Detecting communities in social networks using max-min modularity. In Proceedings of the SIAM international conference on data mining, Sparks, Nevada, USA, April 30–May 2, 2009 (pp. 978–989).

Chen, J., Zaïane, O. R., Goebel, R. (2009b). Local community identification in social networks. In Proceedings of international conference on advances in social network analysis and mining, Athens, Greece, July 20–22, 2009 (pp. 237–242).

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

Clauset, A., Newman, M. E. J., Moore, C. (2004). Finding community structure in very large networks. Physical Review E, 70(6), 066111.CrossRef

Coscia, M., Rossetti, G., Giannotti, F., Pedreschi, D. (2012). Demon: A local-first discovery method for overlapping communities. In Proceedings of the 18th ACM SIGKDD international conference on knowledge discovery and data mining, Beijing, China, August 12–16, 2012 (pp. 615–623).

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

Ester, M., Kriegel, H.-P., Sander, J., Xu, X. (1996). A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the 2nd international conference on knowledge discovery and data mining, Portland, Oregon, USA, August 2–4, 1996 (pp. 226–231).

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

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

Gargi, U., Lu, W., Mirrokni, V. S., Yoon, S. (2011). Large-scale community detection on youtube for topic discovery and exploration. In Proceedings of the 5th international conference on weblogs and social media, Barcelona, Catalonia, Spain, July 17–21, 2011.

Girvan, M., & Newman, M. E. J. (2002). Community structure in social and biological networks. PNAS, 99(12), 7821–7826.CrossRefMATHMathSciNet

Gleich, D. F., & Seshadhri, C. (2012). Vertex neighborhoods, low conductance cuts, and good seeds for local community methods. In Proceedings of the 18th ACM SIGKDD international conference on knowledge discovery and data mining, Beijing, China, August 12–16, 2012 (pp. 597–605).

Huang, J., Sun, H., Han, J., Deng, H., Sun, Y., Liu, Y. (2010). Shrink: A structural clustering algorithm for detecting hierarchical communities in networks. In Proceedings of the 19th ACM conference on information and knowledge management, Toronto, Ontario, Canada, October 26–30, 2010 (pp. 219–228).

Huang, J. B., Sun, H. L., Liu, Y. G., Song, Q. B., Weninger, T. (2011). Towards online multiresolution community detection in large-scale networks. PLOS ONE, 6(8), e23829.CrossRef

Kleinberg, J. M., Kumar, R., Raghavan, P., Rajagopalan, S., Tomkins, A. S. (1999). The web as a graph: Measurements, models, and methods. In Proceedings of 5th annual international conference on computing and combinatorics, Tokyo, Japan, July 26–28, 1999 (pp. 1–17).

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

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

Li, K., & Pang, Y. (2012). A vertex similarity probability model for finding network community structure. In Proceedings of the 16th pacific-asia conference advances in knowledge discovery and data mining, Kuala Lumpur, Malaysia, May 29–June 1, 2012 (pp. 456–467).

Luo, F., Wang, J. Z., Promislow, E. (2006). Exploring local community structures in large networks. In Proceedings of IEEE / WIC / ACM international conference on web intelligence, Hong Kong, China, December 18–22, 2006 (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. In Proceedings of the 15th international conference on data warehousing and knowledge discovery, Prague, Czech Republic, August 26–29, 2013 (pp. 297–308).

Newman, M. E. J. (2004). Fast algorithm for detecting community structure in networks. Physical Review E, 69(6), 066133.CrossRef

Newman, M. E. J. (2006a). Finding community structure in networks using the eigenvectors of matrices. Physical Review E, 74(3), 036104.CrossRef

Newman, M. E. J. (2006b). Modularity and community structure in networks. PNAS, 103(23), 8577–8582.CrossRef

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

Radicchi, F., Castellano, C., Cecconi, F., Loreto, V., Parisi, D. (2004). Defining and identifying communities in networks. Proceedings of the National Academy of Sciences, 101(9), 2658–2663.CrossRef

Raghavan, U. N., Albert, R., Kumara, S. (2007). Near linear time algorithm to detect community structures in large-scale networks. Physical Review E, 76, 036106.CrossRef

Rees, B. S., & Gallagher, K. B. (2010). Overlapping community detection by collective friendship group inference. In Proceedings of international conference on advances in social networks analysis and mining, Odense, Denmark, August 9–11, 2010 (pp. 375–379).

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. In Proceedings of the 10th IEEE international conference on data mining, Sydney, Australia, December 14–17, 2010 (pp. 481–490).

Wasserman, S., & Faust, K. (1994). Social network analysis: Methods and applications. Cambridge: Cambridge University Press.CrossRef

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

Xie, J., Kelley, S., Szymanski, B. K. (2013). Overlapping community detection in networks: The state of the art and comparative study. ACM Computing Surveys, 45(4).

Xu, J. J., & Chen, H. (2005). Crimenet explorer: A framework for criminal network knowledge discovery. ACM Transactions on Information Systems, 23(2), 201–226.CrossRef

Xu, X., Yuruk, N., Feng, Z., Schweiger, T. A. J. (2007). Scan: A structural clustering algorithm for networks. In Proceedings of the 13th ACM SIGKDD international conference on knowledge discovery and data mining, San Jose, California, USA, August 12–15, 2007 (pp. 824–833).

Zachary, W. W. (1977). An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 33, 452–473.

Zhang, W., Pan, G., Wu, Z., Li, S. (2013). Online community detection for large complex networks. In Proceedings of the 23rd international joint conference on artificial intelligence, Beijing, China, August 3–9, 2013 (pp. 1903–1909).

Title: Toward seed-insensitive solutions to local community detection
Authors: Lianhang Ma
Hao Huang
Qinming He
Kevin Chiew
Zhenguang Liu
Publication date: 01-08-2014
Publisher: Springer US
Published in: Journal of Intelligent Information Systems / Issue 1/2014
Print ISSN: 0925-9902
Electronic ISSN: 1573-7675
DOI: https://doi.org/10.1007/s10844-014-0315-6

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/2014

Algorithms for spatial collocation pattern mining in a limited memory environment: a summary of results

OBCAS: an agent-based system and ontology for mobile context aware interactions

Link-based web spam detection using weight properties

Integration operators for generating RDF/OWL-based user defined mediator views in a grid environment

Extensions and relationships of some existing lower-bound functions for dynamic time warping

Multi-view document clustering via ensemble method

Premium Partner