Abstract
We propose a novel, distributed approach for analyzing communities in social networks. In this approach, we define communities from two perspectives: local and global. Firstly, the local communities are identified by each node in a self-centred manner. Then, the global communities are captured using the notion of tendency among local communities. Our approach is especially suitable for decentralised and dynamic networks. We present formal definitions and experimentally verify our model on both static and dynamic networks.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Blondel, V., Guillaume, J., Lambiotte, R., Lefebvre, E.: Fast unfolding of community hierarchies in large networks. Journal of Statistical Mechanics (10), P10008 (2008)
Condon, A., Karp, R.: Algorithms for Graph Partitioning on the Planted Partition Model. Random Struct. Algor. 18, 116–140 (2001)
Evans, T.: Clique graphs and overlapping communities. Journal of Statistical Mechanics: Theory and Experiment 2010, P12037 (2010)
Fortunato, S.:: Community detection in graphs. CoRR abs/0906.0612 (2010)
Gregori, E., Lenzini, L., Mainardi, S.: Parallel k-clique community detection on large-scale networks. IEEE Transactions of Parallel and Distributed Systems 24(8), 1651–1660 (2013)
Girvan, M., Newman, M.: Community structure in social and biological networks. Proceedings of the National Academy of Sciences of the USA 99(12), 7821–7826 (2002)
Harmann, T., Kappes, A., Wagner, D.: Clustering evolving networks. CoRR abs/1401.3516 (2014)
Håstad, J.: Clique is hard to approximate within n 1 − ε. Acta Mathematica 182(1), 105–142 (1999)
Jonsson, P., Cavanna, T., Zicha, D., Bates, P.: Cluster analysis of networks generated through homology: automatic identification of important protein communities involved in cancer metastasis. BMC Bioinformatics 7, 2 (2006)
Kim, S.: Graph theoretic sequence clustering algorithms and their applications to genome comparison. In: Computational Biology and Genome Informatics, pp. 81–116. World Scientific Publishing Company (2003)
Lusseau, D., Newman, M.: Identifying the role that individual animals play in their social network. Proceedings of the Royal Society of London. Series B: Biological Sciences 271(6), 477–481 (2004)
Massaro, E., Olsson, H., Guazzini, A., Bagnoli, F.: Impact of local information in growing networks. In: Proc. of Wivace 2013 – Italian Workshop on Artificial Life and Evolutionary Computation. EPTCS, vol. 130, pp. 53–60 (2013)
Meyers, L., Newman, M., Martin, M., Schrag, S.: Applying network theory to epidemics: Control measures for outbreaks of mycoplasma pneumoniae. Emerging Infectious Diseases 9(2), 204–210 (2003)
Newman, M.: Fast algorithm for detecting community structure in networks. Phys. Rev. E 69, 066133 (2004)
Newman, M.: Coauthorship networks and patterns of scientific collaboration. Proc. Natl. Acad. Sci. USA 101, 5200–5205 (2004)
Newman, M.: Modularity and community structure in networks. Proc. Natl. Acad. Sci. USA 103, 8577–8582 (2006)
Palla, G., Der’enyi, I., Farkas, I., Vicsek, T.: Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, 814–818 (2005)
Porter, M., Onnela, J.-P., Mucha, P.: Communities in networks. Notices of the AMS 56(9), 1082–1097 (2009)
Reddy, P.K., Kitsuregawa, M., Sreekanth, P., Rao, S.S.: A graph based approach to extract a neighborhood customer community for collaborative filtering. In: Bhalla, S. (ed.) DNIS 2002. LNCS, vol. 2544, pp. 188–200. Springer, Heidelberg (2002)
Rossi, R., Gleich, D., Patwary, M.: Parallel maximum clique algorithms with applications to network analysis and storage. CoRR abs/1302.6256 (2013)
Schaeffer, S.: Graph clustering. Computer Science Review 1(1), 27–64 (2007)
Seidman, S.: Network structure and minimum degree. Social Networks 5(3), 269–287 (1983)
Staudt, C., Meyerhenke, H.: Engineering High-Performance Community Detection Heuristics for Massive Graphs. In: Proceedings of the 2013 International Conference on Parallel Processing, pp. 180–189. IEEE (2013)
Shi, J., Xue, W., Wang, W., Zhang, Y., Yang, B., Li, J.: Scalable community detection in massive social networks using MapReduce. IBM Journal of Research and Development 57(3/4), 12 (2013)
Weinstein, C., Campbell, W., Delaney, B., O’Leary, G.: Modeling and Detection Techniques for Counter-Terror Social Network Analysis and Intent Recognition. In: Proc. of IEEE Aerospace Conference, pp. 1–16 (2009)
Yildiz, H., Kruege, C.: Detecting social cliques for automated privacy control in online social networks. In: Proc. of Pervasive Computing and Communications Workshops, pp. 353–359. IEEE (2012)
Zachary, W.: An information flow model for conflict and fission in small groups. Journal of Anthropoloical Research (33), 452–473 (1977)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Liu, J., Wei, Z. (2014). From a Local to a Global Perspective of Community Detection in Networks. In: Pham, DN., Park, SB. (eds) PRICAI 2014: Trends in Artificial Intelligence. PRICAI 2014. Lecture Notes in Computer Science(), vol 8862. Springer, Cham. https://doi.org/10.1007/978-3-319-13560-1_90
Download citation
DOI: https://doi.org/10.1007/978-3-319-13560-1_90
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-13559-5
Online ISBN: 978-3-319-13560-1
eBook Packages: Computer ScienceComputer Science (R0)