Abstract
A major theme in the study of social dynamics is the formation of a community structure on a social network, i.e., the network contains several densely connected region that are sparsely linked between each other. In this paper, we investigate the network integration process in which edges are added to dissolve the communities into a single unified network. In particular, we study the following problem which we refer to as togetherness improvement: given two communities in a network, iteratively establish new edges between the communities so that they appear as a single community in the network. Towards an effective strategy for this process, we employ tools from structural information theory. The aim here is to capture the inherent amount of structural information that is encoded in a community, thereby identifying the edge to establish which will maximize the information of the combined community. Based on this principle, we design an efficient algorithm that iteratively establish edges. Experimental results validate the effectiveness of our algorithm for network integration compared to existing benchmarks.
Z. Zhang—This paper is supported by National Natural Science Foundation of China No. 62172040, No. U1836212, No. 61872041.
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
Similar content being viewed by others
References
Anand, K., Bianconi, G.: Entropy measures for networks: toward an information theory of complex topologies. Phys. Rev. E 80(4), 045102 (2009)
Blondel, V.D., Guillaume, J.L., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. J. Stat. Mech: Theory Exp. 2008(10), P10008 (2008)
Borgatti, S.P., Everett, M.G.: A graph-theoretic perspective on centrality. Soc. Netw. 28(4), 466–484 (2006)
Braunstein, S.L., Ghosh, S., Mansour, T., Severini, S., Wilson, R.C.: Some families of density matrices for which separability is easily tested. Phys. Rev. A 73(1), 012320 (2006)
Brooks, F.P., Jr.: Three great challenges for half-century-old computer science. J. ACM (JACM) 50(1), 25–26 (2003)
Bruhn, J.: The concept of social cohesion. In: Bruhn, J. (ed.) The Group Effect, pp. 31–48. Springer, Boston (2009). https://doi.org/10.1007/978-1-4419-0364-8_2
Cai, Y., Zheng, H., Liu, J., Yan, B., Su, H., Liu, Y.: Balancing the pain and gain of hobnobbing: utility-based network building over atributed social networks. In: Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pp. 193–201 (2018)
Chen, Q., Su, H., Liu, J., Yan, B., Zheng, H., Zhao, H.: In pursuit of social capital: upgrading social circle through edge rewiring. In: Shao, J., Yiu, M.L., Toyoda, M., Zhang, D., Wang, W., Cui, B. (eds.) APWeb-WAIM 2019. LNCS, vol. 11641, pp. 207–222. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26072-9_15
Chunaev, P.: Community detection in node-attributed social networks: a survey. Comput. Sci. Rev. 37, 100286 (2020)
Dehmer, M.: Information processing in complex networks: graph entropy and information functionals. Appl. Math. Comput. 201(1–2), 82–94 (2008)
Fortunato, S., Barthelemy, M.: Resolution limit in community detection. Proc. Natl. Acad. Sci. 104(1), 36–41 (2007)
Fortunato, S., Lancichinetti, A.: Community detection algorithms: a comparative analysis: invited presentation, extended abstract. In: Proceedings of the Fourth International ICST Conference on Performance Evaluation Methodologies and Tools, pp. 1–2 (2009)
Jiang, H., Carroll, J.M.: Social capital, social network and identity bonds: a reconceptualization. In: Proceedings of the Fourth International Conference on Communities and Technologies, pp. 51–60 (2009)
Lancichinetti, A., Fortunato, S., Radicchi, F.: Benchmark graphs for testing community detection algorithms. Phys. Rev. E 78(4), 046110 (2008)
Li, A., Pan, Y.: Structural information and dynamical complexity of networks. IEEE Trans. Inf. Theory 62(6), 3290–3339 (2016)
Liu, J., Wei, Z.: Network, popularity and social cohesion: a game-theoretic approach. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 31 (2017)
Liu, Y., et al.: From local to global norm emergence: dissolving self-reinforcing substructures with incremental social instruments. In: International Conference on Machine Learning, pp. 6871–6881. PMLR (2021)
Liu, Y., Liu, J., Zhang, Z., Zhu, L., Li, A.: REM: from structural entropy to community structure deception. Adv. Neural. Inf. Process. Syst. 32, 12938–12948 (2019)
Moskvina, A., Liu, J.: How to build your network? A structural analysis. arXiv preprint arXiv:1605.03644 (2016)
Moskvina, A., Liu, J.: Integrating networks of equipotent nodes. In: Nguyen, H.T.T., Snasel, V. (eds.) CSoNet 2016. LNCS, vol. 9795, pp. 39–50. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-42345-6_4
Moskvina, A., Liu, J.: Togetherness: an algorithmic approach to network integration. In: 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pp. 223–230. IEEE (2016)
Newman, M.E.: Modularity and community structure in networks. Proc. Natl. Acad. Sci. 103(23), 8577–8582 (2006)
Shalev-Shwartz, S., Ben-David, S.: Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, Cambridge (2014)
Tang, Y., Liu, J., Chen, W., Zhang, Z.: Establishing connections in a social network. In: Geng, X., Kang, B.-H. (eds.) PRICAI 2018. LNCS (LNAI), vol. 11012, pp. 1044–1057. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-97304-3_80
Vitak, J., Ellison, N.B., Steinfield, C.: The ties that bond: re-examining the relationship between Facebook use and bonding social capital. In: 2011 44th Hawaii International Conference on System Sciences, pp. 1–10. IEEE (2011)
Yan, B., Chen, Y., Liu, J.: Dynamic relationship building: exploitation versus exploration on a social network. In: Bouguettaya, A., et al. (eds.) WISE 2017. LNCS, vol. 10569, pp. 75–90. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-68783-4_6
Yan, B., Liu, Y., Liu, J., Cai, Y., Su, H., Zheng, H.: From the periphery to the center: information brokerage in an evolving network. arXiv preprint arXiv:1805.00751 (2018)
Zhao, H., Su, H., Chen, Y., Liu, J., Zheng, H., Yan, B.: A reinforcement learning approach to gaining social capital with partial observation. In: Nayak, A.C., Sharma, A. (eds.) PRICAI 2019. LNCS (LNAI), vol. 11670, pp. 113–117. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-29908-8_9
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 ICST Institute for Computer Sciences, Social Informatics and Telecommunications Engineering
About this paper
Cite this paper
Zhang, S., Liu, J., Liu, Y., Zhang, Z., Khoussainov, B. (2022). Improving Togetherness Using Structural Entropy. In: Deng, S., Zomaya, A., Li, N. (eds) Mobile Computing, Applications, and Services. MobiCASE 2021. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, vol 434. Springer, Cham. https://doi.org/10.1007/978-3-030-99203-3_6
Download citation
DOI: https://doi.org/10.1007/978-3-030-99203-3_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-99202-6
Online ISBN: 978-3-030-99203-3
eBook Packages: Computer ScienceComputer Science (R0)