We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Yu-Xin Ma, Jia-Yi Xu, Di-Chao Peng, Ting Zhang, Cheng-Zhe Jin, Hua-Min Qu, Wei Chen, Qun-Sheng Peng. A Visual Analysis Approach for Community Detection of Multi-Context Mobile Social Networks[J]. Journal of Computer Science and Technology, 2013, 28(5): 797-809. DOI: 10.1007/s11390-013-1378-5
Citation: Yu-Xin Ma, Jia-Yi Xu, Di-Chao Peng, Ting Zhang, Cheng-Zhe Jin, Hua-Min Qu, Wei Chen, Qun-Sheng Peng. A Visual Analysis Approach for Community Detection of Multi-Context Mobile Social Networks[J]. Journal of Computer Science and Technology, 2013, 28(5): 797-809. DOI: 10.1007/s11390-013-1378-5

A Visual Analysis Approach for Community Detection of Multi-Context Mobile Social Networks

Funds: This work is supported by the National Natural Science Foundation of China under Grant Nos. 61232012, 61202279, the National High Technology Research and Development 863 Program of China under Grant No. 2012AA12090, the Natural Science Foundation of Zhejiang Province of China under Grant No. LR13F020001, and the Doctoral Fund of Ministry of Education of China under Grant No. 20120101110134.
More Information
  • Received Date: May 04, 2013
  • Revised Date: August 01, 2013
  • Published Date: September 04, 2013
  • The problem of detecting community structures of a social network has been extensively studied over recent years, but most existing methods solely rely on the network structure and neglect the context information of the social relations. The main reason is that a context-rich network offers too much flxibility and complexity for automatic or manual modulation of the multifaceted context in the analysis process. We address the challenging problem of incorporating context information into the community analysis with a novel visual analysis mechanism. Our approach consists of two stages: interactive discovery of salient context, and iterative context-guided community detection. Central to the analysis process is a context relevance model (CRM) that visually characterizes the influence of a given set of contexts on the variation of the detected communities, and discloses the community structure in specific context configurations. The extracted relevance is used to drive an iterative visual reasoning process, in which the community structures are progressively discovered. We introduce a suite of visual representations to encode the community structures, the context as well as the CRM. In particular, we propose an enhanced parallel coordinates representation to depict the context and community structures, which allows for interactive data exploration and community investigation. Case studies on several datasets demonstrate the effciency and accuracy of our approach.
  • [1]
    Cho E, Myers S A, Leskovec J. Friendship and mobility: User movement in location-based social networks. In Proc. the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 2011, pp.1082-1090.
    [2]
    Scott J, Gass R, Crowcroft J et al. CRAWDAD metadata: Cambridge/haggle/imote/infocom2006 (v. 2009-05-29). http://tinyurl.com/6ugh4nz, August 2013.
    [3]
    Kernighan B W, Lin S. An effcient heuristic procedure for partitioning graphs. Bell System Technical Journal, 1970, 49(2): 291-307.
    [4]
    Girvan M, Newman ME J. Community structure in social and biological networks. Proc. the National Academy of Sciences of the United States of America, 2002, 99(12): 7821-7826.
    [5]
    Newman M E J. Fast algorithm for detecting community structure in networks. Physical Review E, 2004, 69(6): 066133.
    [6]
    Traag V A, Bruggeman J. Community detection in networks with positive and negative links. Physical Review E, 2009, 80(3): 036115.
    [7]
    Tantipathananandh C, Berger-Wolf T, Kempe D. A framework for community identification in dynamic social networks. In Proc. the 13th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, August 2007, pp.717-726.
    [8]
    Eagle N, Pentland A S, Lazer D. Inferring friendship network structure by using mobile phone data. Proc. the National Academy of Sciences of the United States of America, 2009,106(36): 15274-15278.
    [9]
    Blondel V D, Guillaume J L, Lambiotte R et al. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008, 2008(10): P10008.
    [10]
    Hastie T, Tibshirani R, Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd edition). Springer, 2009.
    [11]
    Donetti L, Munoz M A. Detecting network communities: A new systematic and effcient algorithm. Journal of Statistical Mechanics: Theory and Experiment, 2004, 2004: P10012.
    [12]
    Fortunato S. Community detection in graphs. Physics Reports, 2010, 486(3/5): 75-174.
    [13]
    Chen J C, Yuan B. Detecting functional modules in the yeast protein{protein interaction network. Bioinformatics, 2006, 22(18): 2283-2290.
    [14]
    Newman M E J, Girvan M. Finding and evaluating community structure in networks. Physical Review E, 2004, 69(2): 026113.
    [15]
    Mitrovisc M, Tadisac B. Spectral and dynamical properties in classes of sparse networks with mesoscopic inhomogeneities. Physical Review E, 2009, 80(2): 026123.
    [16]
    Garrido P L, Marro J, Munoz M A (eds.). Modeling Cooperative Behavior in the Social Sciences: Eighth Granada Lectures on Modeling Cooperative Behavior in the Social. American Institute of Physics, 2005.
    [17]
    Simonsen I. Diffusion and networks: A powerful combination! Physica A: Statistical Mechanics and Its Applications, 2005, 357(2): 317-330.
    [18]
    Backstrom L, Leskovec J. Supervised random walks: Predicting and recommending links in social networks. In Proc. the 4th ACM International Conference on Web Search and Data Mining, February 2011, pp.635-644.
    [19]
    Zhou H. Distance, dissimilarity index, and network community structure. Physical Review E, 2003, 67(6): 061901.
    [20]
    Ronhovde P, Nussinov Z. Local resolution-limit-free potts model for community detection. Physical Review E, 2010, 81(4): 046114.
    [21]
    Lambiotte R, Delvenne J C, Barahona M. Laplacian dynamics and multiscale modular structure in networks. ArXiv e-prints arXiv:0812.1770, http://arxiv.org/abs/0812.1770, May 2013.
    [22]
    Palla G, Deréenyi I, Farkas I, Vicsek T. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 2005, 435: 814-818.
    [23]
    Gong M G, Zhang L J, Ma J J, Jiao L C. Community detection in dynamic social networks based on multiobjective immune algorithm. Journal of Computer Science and Technology, 2012, 27(3): 455-467.
    [24]
    Chan S Y, Hui P, Xu K. Community detection of time-varying mobile social networks. In Proc. the 1st Int. Conf. Complex Science, Feb. 2009, pp.1154-1159.
    [25]
    Wu Z H, Lin Y F, Gregory S, Wan H Y, Tian S F. Balanced multi-label propagation for overlapping community detection in social networks. Journal of Computer Science and Technology, 2012, 27(3): 468-479.
    [26]
    Wan H Y, Lin Y F, Wu Z H, Huang H K. Discovering typed communities in mobile social networks. Journal of Computer Science and Technology, 2012, 27(3): 480-491.
    [27]
    Wang X, Zhou X, Wang S. Summarizing large-scale database schema using community detection. Journal of Computer Science and Technology, 2012, 27(3): 515-526.
    [28]
    Batagelj V, Mrvar A. Pajek-program for large network analysis. Connections, 1998, 21(2): 47-57.
    [29]
    Heer J, Boyd D. Vizster: Visualizing online social networks. In Proc. IEEE Symposium on Information Visualization, October 2005, pp.32-39.
    [30]
    Smith M A, Shneiderman B, Milic-Frayling N et al. Analyzing (social media) networks with NodeXL. In Proc. the 4th International Conference on Communities and Technologies, June 2009, pp.255-264.
    [31]
    Bastian M, Heymann S, Jacomy M. Gephi: An open source software for exploring and manipulating networks. In Proc. International AAAI Conference on Weblogs and Social Media, May 2009, http://www.aaai.org/ocs/index.php/ ICWSM/09/paper/view/154/1009, Aug. 2013.
    [32]
    Hu Y. Effcient, high-quality force-directed graph drawing. Mathematica Journal, 2005, 10(1): 37-71.
    [33]
    Holten D. Hierarchical edge bundles: Visualization of adjacency relations in hierarchical data. IEEE Transactions on Visualization and Computer Graphics, 2006, 12(5): 741-748.
    [34]
    Wong N, Carpendale S, Greenberg S. Edgelens: An interactive method for managing edge congestion in graphs. In Proc. the 9th IEEE Symp. Inform. Visualization, October 2003, pp.51-58.
    [35]
    Martins R M, Andery G F, Heberle H et al. Multidimensional projections for visual analysis of social networks. Journal of Computer Science and Technology, 2012, 27(4): 791-810.
    [36]
    Collins C, Penn G, Carpendale S. Bubble sets: Revealing set relations with isocontours over existing visualizations. IEEE Transactions on Visualization and Computer Graphics, 2009, 15(6): 1009-1016.
    [37]
    Leguay J, Lindgren A, Scott J, Friedman T, Crowcroft J. Opportunistic content distribution in an urban setting. In Proc. the 2006 SIGCOMM Workshop on Challenged Networks, September 2006, pp.205-212.
    [38]
    Wagstaff K, Cardie C. Clustering with instance-level constraints. In Proc. the 17th Int. Conf. Machine Learning, June 29-July 2, 2000, pp.1103-1110.
  • Related Articles

    [1]Yue Ding, Yu-He Guo, Wei Lu, Hai-Xiang Li, Mei-Hui Zhang, Hui Li, An-Qun Pan, Xiao-Yong Du. Context-Aware Semantic Type Identification for Relational Attributes[J]. Journal of Computer Science and Technology, 2023, 38(4): 927-946. DOI: 10.1007/s11390-021-1048-y
    [2]Yue Kou, De-Rong Shen, Dong Li, Tie-Zheng Nie, Ge Yu. Finding Communities by Decomposing and Embedding Heterogeneous Information Network[J]. Journal of Computer Science and Technology, 2020, 35(2): 320-337. DOI: 10.1007/s11390-020-9957-8
    [3]Huai-Yu Wan, Zhi-Wei Wang, You-Fang Lin, Xu-Guang Jia, Yuan-Wei Zhou. Discovering Family Groups in Passenger Social Networks[J]. Journal of Computer Science and Technology, 2015, 30(5): 1141-1153. DOI: 10.1007/s11390-015-1589-z
    [4]Wen-Gang Zhou, Hou-Qiang Li, Yijuan Lu, Qi Tian. Encoding Spatial Context for Large-Scale Partial-DuplicateWeb Image Retrieval[J]. Journal of Computer Science and Technology, 2014, 29(5): 837-848. DOI: 10.1007/s11390-014-1472-3
    [5]Zhi-Hao Wu, You-Fang Lin, Steve Gregory, Huai-Yu Wan, Student, Sheng-Feng Tian. Balanced Multi-Label Propagation for Overlapping Community Detection in Social Networks[J]. Journal of Computer Science and Technology, 2012, 27(3): 468-479. DOI: 10.1007/s11390-012-1236-x
    [6]Chuan Shi, Zhen-Yu Yan, Xin Pan, Ya-Nan Cai, Bin Wu. A Posteriori Approach for Community Detection[J]. Journal of Computer Science and Technology, 2011, 26(5): 792-805. DOI: 10.1007/s11390-011-0178-z
    [7]Xin Liu, Tsuyoshi Murata. Detecting Communities in K-Partite K-Uniform (Hyper)Networks[J]. Journal of Computer Science and Technology, 2011, 26(5): 778-791. DOI: 10.1007/s11390-011-0177-0
    [8]Yu Guo, Xin-Yu Jiang, Yi-Yun Chen. Certification of Thread Context Switching[J]. Journal of Computer Science and Technology, 2010, 25(4): 827-840. DOI: 10.1007/s11390-010-1064-9
    [9]Ji Wang, Xiao-Dong Ma, Wei Dong, Hou-Feng Xu, Wan-Wei Liu. Demand-Driven Memory Leak Detection Based on Flow- and Context-Sensitive Pointer Analysis[J]. Journal of Computer Science and Technology, 2009, 24(2): 347-356.
    [10]Nan Du, Bai Wang, Bin Wu. Community Detection in Complex Networks[J]. Journal of Computer Science and Technology, 2008, 23(4): 672-683.
  • Cited by

    Periodical cited type(1)

    1. Shao-Feng Zhao, Fang Wang, Bo Liu, et al. LayCO: Achieving Least Lossy Accuracy for Most Efficient RRAM-Based Deep Neural Network Accelerator via Layer-Centric Co-Optimization. Journal of Computer Science and Technology, 2023, 38(2): 328. DOI:10.1007/s11390-023-2545-y

    Other cited types(0)

Catalog

    Article views (43) PDF downloads (6580) Cited by(1)
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return