Department of Mathematics

Combinatorics and Graph Theory

  •  Samin Aref, Max Planck Institute for Demographic Research
  •  Structural analysis of signed graphs: a talk on methods and applications, Zoom
  •  09/23/2020
  •  3:00 PM - 3:50 PM
  •  Online (virtual meeting)

This talk focuses on positive and negative ties in networks (signed graphs) resulting in a common structural configuration. We analyze signed networks from the perspective of balance theory which predicts structural balance as a stable configuration. A signed network is balanced iff its set of vertices can be partitioned into two groups such that positive edges are within the groups and negative edges are between the groups. The scarcity of balanced configurations in networks inferred from empirical data (real networks) requires us to define the notion of partial balance in order to quantify the extent to which a network is balanced. After evaluating several numerical measures of partial balance, we recommend using the frustration index, which equals the minimum number of edges whose removal results in a balanced network []. We use the definition of balance to optimally partition nodes of signed networks into two internally solidary but mutually hostile groups. An optimal partitioning leads to an exact value for the frustration index. We tackle the intensive computations of finding an optimal partition by developing efficient mathematical models and algorithms [] []. We then extend the concepts of balance and frustration in signed networks to applications beyond the classic friend-enemy interpretation of balance theory in the social context. Using a high-performance computer, we analyze large networks to investigate a range of applications from biology, chemistry and physics to finance, international relations, and political science []. In another project manly focused on a political science application, we focus on the challenge of quantifying political polarization in the US Congress, and analyzing its relationship to the fraction of introduced bills that are passed into law (bill passage rate). We use signed graph models of political collaboration among legislators to show that changes in bill passage rates are better explained by the partisanship of a chamber's largest coalition, which we identify by partitioning signed networks of legislators according to balance theory []. In another project, we expand the evaluation of balance to incorporate directionality of the edges and consider three levels of analysis: triads, subgroups, and the whole network. Through extensive computational analysis, we explore common structural patterns across a range of social settings from college students and Wikipedia editors to philosophers and Bitcoin traders. We then apply our multilevel framework of analysis to examine balance in temporal and multilayer networks which leads to new observations on balance with respect to time and layer dimensions [].



Department of Mathematics
Michigan State University
619 Red Cedar Road
C212 Wells Hall
East Lansing, MI 48824

Phone: (517) 353-0844
Fax: (517) 432-1562

College of Natural Science