Abstract
Signed networks form a particular class of complex networks that has many applications in sociology, recommender and voting systems. The contribution of this paper is twofold. First, we propose an approach aimed at determining the characteristic subgraphs of the network. Second, we apply the developed approach to the analysis of the network describing the Wikipedia adminship elections. It is shown that this network agrees with the status theory if one does not consider strongly tied vertices, i.e., the vertices that are connected in both directions. At the same time, the strongly connected vertices mostly agree with the structural balance theory. This result indicates that there is a substantial difference between single and double connections, the fact that deserves a detailed analysis within a broader context of directed signed networks.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Newman, M.: Networks, 2nd edn. Oxford University Press, Oxford (2018)
Chkhartishvili, A.G., Gubanov, D.A., Novikov, D.A.: Social networks: models of information influence, control and confrontation. Studies in Systems, Decision and Control, vol. 189. Springer (2018)
Easley, D., Kleinberg, J.: Networks, Crowds, and Markets. Cambridge University Press, Cambridge (2010)
Newman, M.E.: The structure and function of complex networks. SIAM Rev. 45(2), 167–256 (2003)
Bolouki, S., Nedich, A., Başar, T.: Social networks. In: Handbook of Dynamic Game Theory, pp. 907–949. Springer (2018)
Harary, F.: On the notion of balance of a signed graph. Michigan Math. J. 2(2), 143–146 (1953). https://doi.org/10.1307/mmj/1028989917
Roberts, F.S.: Graph theory and its applications to problems of society. In: Regional conference series in applied mathematics, vol. 29. SIAM (1978)
Kunegis, J.: Applications of structural balance in signed social networks. arXiv: 1402.6865 (2014). https://arxiv.org/abs/1402.6865
Leskovec, J., Huttenlocher, D., Kleinberg, J.: Predicting positive and negative links in online social networks. In: Proceedings of the 19th International Conference on World Wide Web, pp. 641–650 (2010). https://doi.org/10.1145/1772690.1772756
Leskovec, J., Huttenlocher, D., Kleinberg, J.: Signed networks in social media. In: Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, pp. 1361–1370 (2010). https://doi.org/10.1145/1753326.1753532
Pang, B., Lee, L.: Opinion mining and sentiment analysis. Found. Trends R Inf. Retr. 2(1–2), 1–135 (2008)
Marvel, S.A., Kleinberg, J., Kleinberg, R.D., Strogatz, S.H.: Continuous-time model of structural balance. Proc. Nat. Acad. Sci. 108(5), 1771–1776 (2011). https://doi.org/10.1073/pnas.1013213108
Traag, V.A., Van Dooren, P., De Leenheer, P.: Dynamical models explaining social balance and evolution of cooperation. PLoS ONE 8(4), 1–7 (2013). https://doi.org/10.1371/journal.pone.0060063
Shi, G., Proutiere, A., Johansson, M., Baras, J.S., Johansson, K.H.: The evolution of beliefs over signed social networks. Oper. Res. 64(3), 585–604 (2016)
Jia, P., Friedkin, N.E., Bullo, F.: The coevolution of appraisal and influence networks leads to structural balance. IEEE Trans. Netw. Sci. Eng. 3(4), 286–298 (2016). https://doi.org/10.1109/TNSE.2016.2600058
Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., Alon, U.: Network motifs: simple building blocks of complex networks. Science 298(5594), 824–827 (2002)
Itzkovitz, S., Milo, R., Kashtan, N., Ziv, G., Alon, U.: Subgraphs in random networks. Phys. Rev. E 68(2), 026,127 (2003)
Artzy-Randrup, Y., Fleishman, S.J., Ben-Tal, N., Stone, L.: Comment on “Network motifs: simple building blocks of complex networks” and “Superfamilies of evolved and designed networks”. Science 305(5687), 1107 (2004). https://doi.org/10.1126/science.1099334
Milo, R., Itzkovitz, S., Kashtan, N., Levitt, R., Alon, U.: Response to comment on “Network motifs: Simple building blocks of complex networks” and “Superfamilies of evolved and designed networks”. Science 305(5687), 1107 (2004). https://doi.org/10.1126/science.1100519
Harary, F.: Graph Theory. Addison-Wesley, Boston (2018)
Leskovec, J.: Wikipedia adminship election data. Stanford Network Analysis Project. https://snap.stanford.edu/data/wiki-Elec.html
Evmenova, E., Gromov, D.: Structural analysis of directed signed networks. In: Smirnov, N., Golovkina, A. (eds.) Proc. IV Stability and Control Processes Conf. Lecture Notes in Control and Information Sciences. Springer (forthcoming)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Evmenova, E., Gromov, D. (2021). Analysis of Directed Signed Networks: Triangles Inventory. In: Antonyuk, A., Basov, N. (eds) Networks in the Global World V. NetGloW 2020. Lecture Notes in Networks and Systems, vol 181. Springer, Cham. https://doi.org/10.1007/978-3-030-64877-0_8
Download citation
DOI: https://doi.org/10.1007/978-3-030-64877-0_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-64876-3
Online ISBN: 978-3-030-64877-0
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)