Marco Ratta
Introducing fractionalization index in Balance theory.
Rel. Giacomo Como, Claudio Altafini. Politecnico di Torino, Corso di laurea magistrale in Ingegneria Matematica, 2022

PDF (Tesi_di_laurea)
 Tesi
Licenza: Creative Commons Attribution Noncommercial No Derivatives. Download (13MB)  Preview 
Abstract: 
In a world which is every day more interconnected and permeated with social relationships (both physical and virtual) modelling such interactions has become an interesting point mostly to achieve a better comprehension of phenomena such as the raise of communities. From a mathematical perspective the general theory of unsigned networks  where nodes are linked one to each others by positive arcs representing the intensity of the links  seems not optimal to describe such situations and signed networks are commonly used in order to take into account also negative interactions (enmity). Referring to Cartwright and Harary's generalization of Heider's theory, the two theories of structural balance and weak balance have been developed in order to investigate the cause of conflicts in networks of individuals whose mutual relationships are characterizable in terms of friendship and hostility. In this regard the structural balance theory postulates that origin of such tensions is related to the presence of negative cycles, meaning that a network is exactly balanced if it has no negative cycles while it is increasingly unbalanced the more the negative cycles are present in the network. Relaxing the hypothesis allowing the network to have "weakly balanced cycles" (i.e. negative cycles with more than one negative link) the weak balance theory instead generalizes the previous one postulating that a network is balanced if it can be exactly partitioned into communities where every withincommunity link is positive and every betweencommunities link is negative, while it is increasingly unbalanced the more is the amount of unbalanced cycles. As it is hard to expect that real networks are exactly balanced particularly interesting is determining how far a network is from its balance; in this regard among the various methods introduced in literature one of interest is the frustration index (also known as line index of imbalance) which represents the minimum number of edges to reverse in order to achieve a balanced transformation of the network. Despite its simple derivation though, its computation turns out to be an NP hard problem (which not allows it to be calculated for large networks) and heuristics have been proposed to estimate it in a feasible time. For the case of weakly balanced fully connected networks and supposing the related partition of the network is known though, we prove that the frustration index is related to the fractionalization  a dispersion index well known in literature and vastly used in economy and ecology  by an exact formula. Being that the two indexes are well correlated in the vast majority of the cases two consequences follow: from one hand knowing the network partition we can interpret fractionalization as an easy to compute estimation of the frustration, secondly, we can use frustration to estimate the number of expected communities in community detection algorithms. Aim of this work is to prove these concepts in the cases of fully connected networks, Erdos Renyi networks and quasi weakly balanced networks. For all these cases the exact formula for the frustration index is obtained and demonstrated numerically using artificial networks, moreover for the fully connected case some examples of real networks belonging to economy, politics and etnolinguistic are brought in order to validate the formula. Lastly a novel approach for community detection is proposed and compared with the state of the art for unsigned and signed networks in the case of planted partition graphs. 

Relators:  Giacomo Como, Claudio Altafini 
Academic year:  2022/23 
Publication type:  Electronic 
Number of Pages:  79 
Subjects:  
Corso di laurea:  Corso di laurea magistrale in Ingegneria Matematica 
Classe di laurea:  New organization > Master science > LM44  MATHEMATICAL MODELLING FOR ENGINEERING 
Aziende collaboratrici:  Linköping University 
URI:  http://webthesis.biblio.polito.it/id/eprint/24046 
Modify record (reserved for operators) 