Weitere Artikel dieser Ausgabe durch Wischen aufrufen
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.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
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., & 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.
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).
- Toward seed-insensitive solutions to local community detection
- Springer US
Neuer Inhalt/© ITandMEDIA, Product Lifecycle Management/© Eisenhans | vege | Fotolia