Abstract
Structural 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 of network analysis. Due to its definition, the detection of structural hole spanners relies on the partitioning of subgraph or community structures in network, but most existing methods for detecting structural hole spanner rely on known community labels or complex global search, which are difficult to apply to large-scale real-world networks without labels. To address the aforementioned challenges, inspired by success of graph contrastive learning, we propose a self-supervised method for jointly detecting community and structural hole spanner, i.e., a Augmentation-Free contrastive learning framework for jointly detecting Community and structural hole spanner, named AF-Comm. Experimental results on multiple real-world networks demonstrate the superiority of our algorithm on both community detection and structural hole spanner detection tasks.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Barnard, S.T., Simon, H.D.: Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems. Concurr. Practi. Exp. 6(2), 101–117 (1994)
Bielak, P., Kajdanowicz, T., Chawla, N.V.: Graph Barlow twins: a self-supervised representation learning framework for graphs. Knowl.-Based Syst. 256, 109631 (2022)
Burt, R.S.: Structural Holes: The Social Structure of Competition. Harvard University Press (1995)
Burt, R.S., Kilduff, M., Tasselli, S.: Social network analysis: foundations and frontiers on advantage. Annu. Rev. Psychol. 64, 527–547 (2013)
Chen, T., Kornblith, S., Norouzi, M., Hinton, G.: A simple framework for contrastive learning of visual representations. In: International Conference on Machine Learning, pp. 1597–1607. PMLR (2020)
Giles, C.L., Bollacker, K.D., Lawrence, S.: Citeseer: an automatic citation indexing system. In: Proceedings of the Third ACM Conference on Digital Libraries, pp. 89–98 (1998)
Girvan, M., Newman, M.E.: Community structure in social and biological networks. Proc. Natl. Acad. Sci. 99(12), 7821–7826 (2002)
Grill, J.B., et al.: Bootstrap your own latent-a new approach to self-supervised learning. Adv. Neural. Inf. Process. Syst. 33, 21271–21284 (2020)
Guo, X., Gao, L., Liu, X., Yin, J.: Improved deep embedded clustering with local structure preservation. In: IJCAI, pp. 1753–1759 (2017)
Hamilton, W., Ying, Z., Leskovec, J.: Inductive representation learning on large graphs. In: Advances in Neural Information Processing Systems, vol. 30 (2017)
He, L., Lu, C.T., Ma, J., Cao, J., Shen, L., Yu, P.S.: Joint community and structural hole spanner detection via harmonic modularity. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 875–884 (2016)
Hjelm, R.D., et al.: Learning deep representations by mutual information estimation and maximization. arXiv preprint arXiv:1808.06670 (2018)
Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2016)
Kipf, T.N., Welling, M.: Variational graph auto-encoders. arXiv preprint arXiv:1611.07308 (2016)
Lee, N., Lee, J., Park, C.: Augmentation-free self-supervised learning on graphs. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 36, pp. 7372–7380 (2022)
Li, F., Zou, Z., Li, J., Li, Y., Chen, Y.: Distributed parallel structural hole detection on big graphs. In: Li, G., Yang, J., Gama, J., Natwichai, J., Tong, Y. (eds.) DASFAA 2019. LNCS, vol. 11446, pp. 519–535. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-18576-3_31
Lin, S., Hu, Q., Wang, G., Yu, P.S.: Understanding community effects on information diffusion. In: Cao, T., Lim, E.-P., Zhou, Z.-H., Ho, T.-B., Cheung, D., Motoda, H. (eds.) PAKDD 2015. LNCS (LNAI), vol. 9077, pp. 82–95. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-18038-0_7
Lou, T., Tang, J.: Mining structural hole spanners through information diffusion in social networks. In: Proceedings of the 22nd international conference on World Wide Web, pp. 825–836 (2013)
Ma, X., et al.: A comprehensive survey on graph anomaly detection with deep learning. IEEE Trans. Knowl. Data Eng. (2021)
McCallum, A.K., Nigam, K., Rennie, J., Seymore, K.: Automating the construction of internet portals with machine learning. Inf. Retrieval 3, 127–163 (2000)
Page, L., Brin, S., Motwani, R., Winograd, T.: The pagerank citation ranking: bringing order to the web. Technical report, Stanford InfoLab (1999)
Rezvani, M., Liang, W., Xu, W., Liu, C.: Identifying top-k structural hole spanners in large-scale social networks. In: Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, pp. 263–272 (2015)
Sen, P., Namata, G., Bilgic, M., Getoor, L., Galligher, B., Eliassi-Rad, T.: Collective classification in network data. AI Mag. 29(3), 93–93 (2008)
Shchur, O., Mumme, M., Bojchevski, A., Günnemann, S.: Pitfalls of graph neural network evaluation. arXiv preprint arXiv:1811.05868 (2018)
Song, C., Hsu, W., Lee, M.L.: Mining brokers in dynamic social networks. In: Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, pp. 523–532 (2015)
Sun, M., Xing, J., Wang, H., Chen, B., Zhou, J.: MOCL: data-driven molecular fingerprint via knowledge-aware contrastive learning from molecular graph. In: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 3585–3594 (2021)
Thakoor, S., Tallec, C., Azar, M.G., Munos, R., Veličković, P., Valko, M.: Bootstrapped representation learning on graphs. In: ICLR 2021 Workshop on Geometrical and Topological Representation Learning (2021)
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., Bengio, Y.: Graph attention networks. arXiv preprint arXiv:1710.10903 (2017)
Velickovic, P., Fedus, W., Hamilton, W.L., Liò, P., Bengio, Y., Hjelm, R.D.: Deep graph infomax. ICLR (Poster) 2(3), 4 (2019)
Wang, C., Pan, S., Hu, R., Long, G., Jiang, J., Zhang, C.: Attributed graph clustering: a deep attentional embedding approach. arXiv preprint arXiv:1906.06532 (2019)
Winterbach, W., Mieghem, P.V., Reinders, M., Wang, H., Ridder, D.d.: Topology of molecular interaction networks. BMC Syst. Biol. 7, 1–15 (2013)
Xie, J., Girshick, R., Farhadi, A.: Unsupervised deep embedding for clustering analysis. In: International Conference on Machine Learning, pp. 478–487. PMLR (2016)
Xu, W., Li, T., Liang, W., Yu, J.X., Yang, N., Gao, S.: Identifying structural hole spanners to maximally block information propagation. Inf. Sci. 505, 100–126 (2019)
Zhang, T., Xiong, Y., Zhang, J., Zhang, Y., Jiao, Y., Zhu, Y.: CommdGI: community detection oriented deep graph infomax. In: Proceedings of the 29th ACM International Conference on Information and Knowledge Management, pp. 1843–1852 (2020)
Zhang, Y., et al.: Finding structural hole spanners based on community forest model and diminishing marginal utility in large scale social networks. Knowl.-Based Syst. 199, 105916 (2020)
Zhu, X., Lafferty, J., Ghahramani, Z.: Combining active learning and semi-supervised learning using gaussian fields and harmonic functions. In: ICML 2003 Workshop on the Continuum from labeled to Unlabeled Data in Machine Learning and Data Mining, vol. 3 (2003)
Zhu, Y., Xu, Y., Yu, F., Liu, Q., Wu, S., Wang, L.: Deep graph contrastive representation learning. arXiv preprint arXiv:2006.04131 (2020)
Zhu, Y., Xu, Y., Yu, F., Liu, Q., Wu, S., Wang, L.: Graph contrastive learning with adaptive augmentation. In: Proceedings of the Web Conference 2021, pp. 2069–2080 (2021)
Acknowledgments
This work is supported by the Shenzhen Sustainable Development Project under Grant (KCXFZ20201221173013036) and NSFC program (No. 62272338).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Zhang, J., Wang, W., Li, T., Shao, M., Liu, J., Sun, Y. (2023). Joint Community and Structural Hole Spanner Detection via Graph Contrastive Learning. In: Jin, Z., Jiang, Y., Buchmann, R.A., Bi, Y., Ghiran, AM., Ma, W. (eds) Knowledge Science, Engineering and Management. KSEM 2023. Lecture Notes in Computer Science(), vol 14120. Springer, Cham. https://doi.org/10.1007/978-3-031-40292-0_33
Download citation
DOI: https://doi.org/10.1007/978-3-031-40292-0_33
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-40291-3
Online ISBN: 978-3-031-40292-0
eBook Packages: Computer ScienceComputer Science (R0)