Modeling acquaintance networks based on balance theory

Vukašinović, V. ; Šilc, J. ; Škrekovski, R.

International Journal of Applied Mathematics and Computer Science, Tome 24 (2014) no. 3, pp. 683-696.

Résumé

An acquaintance network is a social structure made up of a set of actors and the ties between them. These ties change dynamically as a consequence of incessant interactions between the actors. In this paper we introduce a social network model called the Interaction-Based (IB) model that involves well-known sociological principles. The connections between the actors and the strength of the connections are influenced by the continuous positive and negative interactions between the actors and, vice versa, the future interactions are more likely to happen between the actors that are connected with stronger ties. The model is also inspired by the social behavior of animal species, particularly that of ants in their colony. A model evaluation showed that the IB model turned out to be sparse. The model has a small diameter and an average path length that grows in proportion to the logarithm of the number of vertices. The clustering coefficient is relatively high, and its value stabilizes in larger networks. The degree distributions are slightly right-skewed. In the mature phase of the IB model, i.e., when the number of edges does not change significantly, most of the network properties do not change significantly either. The IB model was found to be the best of all the compared models in simulating the e-mail URV (University Rovira i Virgili of Tarragona) network because the properties of the IB model more closely matched those of the e-mail URV network than the other models.

Détail

Keywords: social network, small-world, balance theory, pheromone infrastructure
Mots-clés : sieć społeczna, małe światy, teoria równowagi

Bibliographie

[1] Antal, T., Krapivsky, P.L. and Redner, S. (2005). Dynamics of social balance on networks, Physical Review E 72(3): 036121.

[2] Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks, Science 286(5439): 509–512.

[3] Camazine, S., Deneubourg, J.-L., Franks, N.R., Sneyd, J., Théraulaz, G. and Bonabeau, E. (2001). Self-Organization in Biological Systems, Princeton University Press, Princeton, NJ.

[4] Davidsen, J., Ebel, H. and Bornholdt, S. (2002). Emergence of a small world from local interactions: Modeling acquaintance networks, Physical Review Letters 88(12): 128701.

[5] de Sola Pool, I. and Kochen, M. (1978). Contacts and influence, Social Networks 1(1): 5–58.

[6] Dorigo, M., Bonabeau, E. and Th´eraulaz, G. (2000). Ant algorithms and stigmergy, Future Generation Computer Systems 16(9): 851–871.

[7] Dorigo, M., Maniezzo, V. and Colorni, A. (1996). The ant system: Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics B 26(1): 29–41.

[8] Erdös, P. and Rényi, A. (1960). On the evolution of random graphs, Publications of the Mathematical Institute of the Hungarian Academy of Sciences 5(1–2): 17–61.

[9] Freeman, L.C. (2004). The Development of Social Network Analysis: A Study in the Sociology of Science, Empirical Press, Vancouver, BC.

[10] Granovetter, M.S. (1973). The strength of weak ties, American Journal of Sociology 78(6): 1360–1380.

[11] Grassé, P.-P. (1959). La reconstruction du nid et les coordinations inter-individuelles chez Bellicositermes natalensis et Cubitermes sp. La théorie de la stigmergie: Essai d’interprétation du comportement des termites constructeurs, Insectes Sociaux 6(1): 41–81.

[12] Grossetti, M. (2005). Where do social relations come from? A study of personal networks in the Toulouse area of France, Social Networks 27(4): 289–301.

[13] Guimerà, R., Danon, L., Diaz-Guilera, A., Giralt, F. and Arenas, A. (2003). Self-similar community structure in a network of human interactions, Physical Review E 68(6): 065103(R).

[14] Handl, J., Knowles, J. and Dorigo, M. (2006). Ant based clustering and topographic mapping, Artificial Life 12(1): 35–61.

[15] Heider, F. (1946). Attitudes and cognitive organization, Journal of Psychology 21(1): 107–112.

[16] Jiang, J., Wang, R. and Wang, Q.A. (2011). Network model of deviation from power-law distribution in complex network, The European Physical Journal B 79(1): 29–33.

[17] Korošec P. (2006). Stigmergy as an Approach to Metaheuristic Optimization, Ph.D. thesis, Jožef Stefan International Postgraduate School, Ljubljana.

[18] Korošec, P., Šilc, J. and Filipič, B. (2012). The differential ant-stigmergy algorithm, Information Sciences 192(1): 82–97.

[19] Kumpula, J.M., Onnela, J., Saramäki, J., Kaski, K. And Kertesz, J. (2007). Emergence of communities in weighted networks, Physical Review Letters 99(22): 228701.

[20] Kleinberg, J.M. (2000). The small-world phenomenon: An algorithmic perspective, Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, Portland, OR, USA, pp. 163–173.

[21] Leskovec, J. (2010). Kronecker graphs: An approach to modeling networks, Journal of Machine Learning Research 11: 985–1042.

[22] Ludwig, M. and Abell, P. (2007). An evolutionary model of social networks, European Physical Journal B 58(1): 97–105.

[23] Marsili, M., Vega-Redondo, F. and Slanina, F. (2004). The rise and fall of a networked society: A formal model, Proceedings of the National Academy of Sciences of the United mStates of America 101(6): 1439–1442.

[24] Martens, D., De Backer, M., Haesen, R., Vanthienen, J., Snoeck, M. and Baesens, B. (2007). Classification with ant colony optimization, IEEE Transactions on Evolutionary Computation 11(5): 651–665.

[25] Marvel, S.A., Kleinberg, J., Kleinberg, R.D., and Strogatz, S.H. (2011). Continuous-time model of structural balance, Proceedings of the National Academy of Sciences of the United States of America 108(5):1771–1776.

[26] Milgram, S. (1967). The small world problem, Psychology Today 1(1): 61–67.

[27] Newman,M.E.J. (2001). The structure of scientific collaboration networks, Proceedings of the National Academy of Sciences of the United States of America 98(2): 404–409.

[28] Newman, M.E.J. (2008). Mathematics of Networks, Palgrave Macmillan, Basingstoke.

[29] Péter, T. (2012). Modeling nonlinear road traffic networks for junction control, International Journal of Applied Mathematics and Computer Science 22(3): 723–732, DOI: 10.2478/v10006-012-0054-1.

[30] Pons, P. and Latapy,M. (2005). Computing communities in large networks using random walks, arXiv:physics/0512106v1.

[31] Rand, W.M. (1971). Objective criteria for the evaluation of clustering methods, Journal of the American Statistical Association 66(336): 846–850.

[32] Rapoport, A. (1957). Contribution to the theory of random and biased nets, Bulletin of Mathematical Biology 19(4): 257–277.

[33] Srinivasan, A. (2011). Local balancing influences global structure in social networks, Proceedings of the National Academy of Sciences of the United States of America 108(5): 1751–1752.

[34] Toivonen, R., Kovanen, L., Kivelä, M., Onnela, J., Saramäki, J. and Kaski, K. (2009). A comparative study of social network models: Network evolution models and nodal attribute models, Social Networks 31(4): 240–254.

[35] Vukašinović, V., Šilc, J. and Škrekovski, R. (2012a). Towards social networks model, Proceedings of the 5th International Conference on Bioinspired Optimization Methods and Their Applications, Bohinj, Slovenia, pp. 49–60.

[36] Vukašinović, V., Šilc, J. and Škrekovski, R. (2012b). Swarm-inspired social network model and its properties, Proceedings of the 4th International Conference on Information Technologies and Information Society, Novo Mesto, Slovenia.

[37] Wang, W., Hu, B., Zhou, T., Wang, B. and Xie, Y. (2005). Mutual selection model for weighted networks, Physical Review E 72(4): 046140.

[38] Watts, D.J. (1999). Small Worlds: The Dynamics of Networks Between Order and Randomness, Princeton University Press, Princeton, NJ.

[39] Watts, D.J. and Strogatz, S.H. (1998). Collective dynamics of ‘small-world’ networks, Nature 393(6684): 440–442.

[40] White, D.R., Kejzar, N., Tsallis, C., Farmer, D. and White, S. (2006). A generative model for feedback networks, Physical Review E 73(1): 016119.

[41] Wynne, C.D.L. (2001). Animal Cognition: The Mental Lives of Animals, Palgrave Macmillan, Basingstoke.

[42] Xiong, F., Liu, Y., Zhu, J., Zhang, Z.J., Zhang, Y.C. and Zhang, Y. (2011). A dissipative network model with neighboring activation, The European Physical Journal B 84(1): 115–120.