Abstract
The extent to which a node occupies a central position in a social network amounts to a crucial indicator of personal influence. Few works address the mechanisms that would allow an individual to integrate into a network, and even fewer examine the correlation between this process and various notions of centrality. In this paper, we tackle this problem by focusing on the process in which a newcomer joins a network through building connections and gains centrality. We provide three efficient heuristics that build edges between the newcomer and existing members of a social network and compare their performances in terms of three centrality metrics. We perform experiments on random graphs generated by two synthetic network models and four real-world networks. Not only our heuristics considerably outperform the random benchmark algorithm, but the results also reveal some new insights that are related to centrality and network topology. In particular, the results distinguish between measures along two dimensions: the first concerns with the number of centers in a network, and the second concerns with the type of involvement of a node in the network.
This work was supported by the Major Project of National Social Science of China (14ZDB016).
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
Borgatti, S.P., Everett, M.G.: A graph-theoretic perspective on centrality. Soc. Netw. 28(4), 466–484 (2006)
Chen, W., Wang, Y., Yang, S.: Efficient influence maximization in social networks. In: ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 199–208 (2009)
Crescenzi, P., D’Angelo, G., Severini, L., Velaj, Y.: Greedily Improving Our Own Centrality in A Network. In: Bampis, E. (ed.) SEA 2015. LNCS, vol. 9125, pp. 43–55. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-20086-6_4
Csima, B.F., Khoussainov, B., Liu, J.: Computable categoricity of graphs with finite components. In: Beckmann, A., Dimitracopoulos, C., Löwe, B. (eds.) CiE 2008. LNCS, vol. 5028, pp. 139–148. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-69407-6_15
Freeman, L.C.: A set of measures of centrality based on betweenness. Sociometry 40(1), 35–41 (1977)
Gargiulo, M., Benassi, M.: Trapped in your own net? Network cohesion, structural holes, and the adaptation of social capital. Organ. Sci. 11(2), 183–196 (2000)
Granovetter, M.S.: The strength of weak ties. Am. J. Sociol. 78(6), 1360–1380 (1973)
Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence through a social network. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137–146 (2003)
Khoussainov, B., Liu, J., Khaliq, I.: A dynamic algorithm for reachability games played on trees. In: Královič, R., Niwiński, D. (eds.) MFCS 2009. LNCS, vol. 5734, pp. 477–488. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03816-7_41
Kleinberg, J., Suri, S., Wexler, T.: Strategic network formation with structural holes. ACM SIGecom Exch. 7(3), 11 (2008)
Liu, J., Wei, Z.: Community detection based on graph dynamical systems with asynchronous runs. In: Computing and Networking (CANDAR) Second International Symposium on 2014, pp. 463–469. IEEE (2014)
Liu, J., Wei, Z.: Network, popularity and social cohesion: a game-theoretic approach. In: AAAI, pp. 600–606 (2017)
Lü, L., Chen, D., Ren, X.L., Zhang, Q.M., Zhang, Y.C., Zhou, T.: Vital nodes identification in complex networks. Physics reports, vol. 650, pp. 1–63 (2016)
Moskvina, A., Liu, J.: How to build your network? A structural analysis. In: Proceedings of IJCAI 2016 (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: IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2017, pp. 223–230 (2016)
Puzis, R., Zilberman, P., Elovici, Y., Dolev, S., Brandes, U.: Heuristics for speeding up betweenness centrality computation. In: Privacy, Security, Risk and Trust, pp. 302–311 (2012)
Rossi, R., Ahmed, K.: The network data repository with interactive graph analytics and visualization. In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (2015)
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)
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Tang, Y., Liu, J., Chen, W., Zhang, Z. (2018). Establishing Connections in a Social Network. In: Geng, X., Kang, BH. (eds) PRICAI 2018: Trends in Artificial Intelligence. PRICAI 2018. Lecture Notes in Computer Science(), vol 11012. Springer, Cham. https://doi.org/10.1007/978-3-319-97304-3_80
Download citation
DOI: https://doi.org/10.1007/978-3-319-97304-3_80
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-97303-6
Online ISBN: 978-3-319-97304-3
eBook Packages: Computer ScienceComputer Science (R0)