Lifang He
ABSTRACT
Detecting communities (or modular structures) and structural hole spanners, the nodes bridging different communities in a network, are two essential tasks in the realm of network analytics. Due to the topological nature of communities and structural hole spanners, these two tasks are naturally tangled with each other, while there has been little synergy between them. In this paper, we propose a novel harmonic modularity method to tackle both tasks simultaneously. Specifically, we apply a harmonic function to measure the smoothness of community structure and to obtain the community indicator. We then investigate the sparsity level of the interactions between communities, with particular emphasis on the nodes connecting to multiple communities, to discriminate the indicator of SH spanners and assist the community guidance. Extensive experiments on real-world networks demonstrate that our proposed method outperforms several state-of-the-art methods in the community detection task and also in the SH spanner identification task (even the methods that require the supervised community information). Furthermore, by removing the SH spanners spotted by our method, we show that the quality of other community detection methods can be further improved.
Supplemental Material
- D. S. Bassett, E. T. Bullmore, A. Meyer-Lindenberg, J. A. Apud, D. R. Weinberger, and R. Coppola. Cognitive fitness of cost-efficient brain functional networks. PNAS, 106(28):11747--11752, 2009.Google Scholar
Cross Ref
- U. Brandes. A faster algorithm for betweenness centrality*. Journal of Mathematical Sociology, 25(2):163--177, 2001.Google ScholarCross Ref
- R. S. Burt. Secondhand brokerage: Evidence on the importance of local structure for managers, bankers, and analysts. Academy of Management Journal, 50:119--148, 2007.Google ScholarCross Ref
- R. S. Burt. Structural holes: The social structure of competition. Harvard university press, 2009.Google Scholar
- V. Buskens and A. Van de Rijt. Dynamics of networks if everyone strives for structural holes1. American Journal of Sociology, 114(2):371--407, 2008.Google ScholarCross Ref
- K. Ciesielski, D. Czerski, M. Dramiński, M. A. Kłopotek, and S. T. Wierzchoń. Semantic information within the beatca framework. Control and Cybernetics, 39(2):377--400, 2010.Google Scholar
- A. Clauset, M. E. Newman, and C. Moore. Finding community structure in very large networks. Physical review E, 70(6):066111, 2004.Google Scholar
- G. Cordasco and L. Gargano. Community detection via semi-synchronous label propagation algorithms. In BASNA, pages 1--8, 2010.Google ScholarCross Ref
- I. S. Dhillon, Y. Guan, and B. Kulis. Weighted graph cuts without eigenvectors a multilevel approach. TPAMI, 29(11):1944--1957, 2007. Google ScholarDigital Library
- S. Fortunato. Community detection in graphs. Physics reports, 486(3):75--174, 2010.Google ScholarCross Ref
- M. Girvan and M. E. Newman. Community structure in social and biological networks. PNAS, 99(12):7821--7826, 2002.Google ScholarCross Ref
- A. Goyal, W. Lu, and L. V. Lakshmanan. Celf: optimizing the greedy algorithm for influence maximization in social networks. In WWW, pages 47--48, 2011. Google ScholarDigital Library
- S. Goyal and F. Vega-Redondo. Structural holes in social networks. Journal of Economic Theory, 137(1):460--492, 2007.Google ScholarCross Ref
- A. A. Hagberg, D. A. Schult, and P. J. Swart. Exploring network structure, dynamics, and function using NetworkX. In SciPy, pages 11--15, 2008.Google Scholar
- R. He, T. Tan, L. Wang, and W.-S. Zheng. l2,1 regularized correntropy for robust feature selection. In CVPR, pages 2504--2511, 2012. Google ScholarDigital Library
- U. Kang and C. Faloutsos. Beyond'caveman communities,: Hubs and spokes for graph compression and mining. In ICDM, pages 300--309, 2011. Google ScholarDigital Library
- D. Kempe, J. Kleinberg, and É. Tardos. Maximizing the spread of influence through a social network. In KDD, pages 137--146, 2003. Google ScholarDigital Library
- J. Kleinberg, S. Suri, É. Tardos, and T. Wexler. Strategic network formation with structural holes. In EC, pages 284--293, 2008. Google ScholarDigital Library
- S. Lin, Q. Hu, G. Wang, and S. Y. Philip. Understanding community effects on information diffusion. In PAKDD, pages 82--95, 2015.Google ScholarCross Ref
- T. Lou and J. Tang. Mining structural hole spanners through information diffusion in social networks. In WWW, pages 825--836, 2013. Google ScholarDigital Library
- M. E. Newman. Modularity and community structure in networks. PNAS, 103(23):8577--8582, 2006.Google ScholarCross Ref
- M. E. Newman and M. Girvan. Finding and evaluating community structure in networks. Physical review E, 69(2):026113, 2004.Google Scholar
- A. Y. Ng, M. I. Jordan, Y. Weiss, et al. On spectral clustering: Analysis and an algorithm. NIPS, 2:849--856, 2002. Google ScholarDigital Library
- F. Nie, H. Huang, X. Cai, and C. H. Ding. Efficient and robust feature selection via joint l2, 1-norms minimization. In NIPS, pages 1813--1821, 2010.Google ScholarDigital Library
- M. Nikolova and M. K. Ng. Analysis of half-quadratic minimization methods for signal and image recovery. SISC, 27(3):937--966, 2005. Google ScholarDigital Library
- L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: bringing order to the web. 1999.Google Scholar
- J. M. Podolny and J. N. Baron. Resources and relationships: Social networks and mobility in the workplace. American Sociological Review, 62(5):673, 1997.Google ScholarCross Ref
- M. Rezvani, W. Liang, W. Xu, and C. Liu. Identifying top-k structural hole spanners in large-scale social networks. In CIKM, pages 263--272, 2015. Google ScholarDigital Library
- M. Rosvall and C. T. Bergstrom. Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems. PloS one, 6(4):e18209, 2011.Google ScholarCross Ref
- Y. Ruan and S. Parthasarathy. Simultaneous detection of communities and roles from large networks. In COSN, pages 203--214, 2014. Google ScholarDigital Library
- D. A. Spielman. Algorithms, graph theory, and linear equations in laplacian matrices. In ICM, volume 4, pages 2698--2722, 2010.Google Scholar
- J. Tang, T. Lou, and J. Kleinberg. Inferring social ties across heterogenous networks. In WSDM, pages 743--752, 2012. Google ScholarDigital Library
- M. P. van den Heuvel and O. Sporns. Rich-club organization of the human connectome. The Journal of neuroscience, 31(44):15775--15786, 2011.Google ScholarCross Ref
- L. Wang, T. Lou, J. Tang, and J. E. Hopcroft. Detecting community kernels in large social networks. In ICDM, pages 784--793, 2011. Google ScholarDigital Library
- Z. Wang, Z. Chen, Y. Zhao, and S. Chen. A community detection algorithm based on topology potential and spectral clustering. The Scientific World Journal, 2014.Google ScholarCross Ref
- W. Winterbach, P. Van Mieghem, M. Reinders, H. Wang, and D. de Ridder. Topology of molecular interaction networks. BMC systems biology, 7(1):90, 2013.Google Scholar
- J. Yang and J. Leskovec. Defining and evaluating network communities based on ground-truth. KAIS, 42(1):181--213, 2015. Google ScholarDigital Library
- W. W. Zachary. An information flow model for conflict and fission in small groups. Journal of anthropological research, pages 452--473, 1977.Google Scholar
Index Terms
- Joint Community and Structural Hole Spanner Detection via Harmonic Modularity
Recommendations
Joint Community and Structural Hole Spanner Detection via Graph Contrastive Learning
Knowledge Science, Engineering and ManagementAbstractStructural hole spanners are nodes in a network that connect different communities, which are located on key information paths and control information flow between different communities, and therefore have an important status from the perspective ...
Community detection based on modularity and k-plexes
Highlights- We define community seeds and propose a novel community detection method MOKP.
- ...
AbstractCommunity identification is of great worth for analyzing the structure or characteristics of a complex network. Many community detection methods have been developed, such as modularity-based optimization models, which are widely used ...
Modularity approach for community detection in complex networks
IMCOM '17: Proceedings of the 11th International Conference on Ubiquitous Information Management and CommunicationCommunity detection has been one of the relevant areas in the field of graph mining. It imposes a significant challenge to computer scientists, physicists, and sociologists alike, to identify and discover community for large graph with over millions of ...
Comments