Signed Network Structural Analysis and Applications​

Vortrag im Kolloquium Informatik von Dr. Samin Aref

Freitag, 11.01.2019, 16:15 Uhr, Raum D 239

 

Referent: Dr. Samin Aref (Max Planck Institute for Demographic Research)

Gastgeber: Prof. Dr. Steffen Staab, Dr. Oul Han

Titel: Signed Network Structural Analysis and Applications​

Abstract:

This talk focuses on small-scale properties of certain networks resulting in global structure in larger scales. Graph-theoretic conditions are used to determine the structural properties exhibited by the networks. Our focus is on signed networks which have positive and negative edges. We analyse such networks from the perspective of balance theory which predicts structural balance as a global structure for signed social networks that represent groups of friends and enemies. The vertex set of  balanced signed networks can be partitioned into two subsets such that each negative edge joins vertices belonging to different subsets.

The scarcity of balanced networks encouraged us to define the notion of partial balance in order to quantify the extent to which a network is balanced. We evaluate several numerical measures of partial balance and recommend using the frustration index, a measure that satisfies key axiomatic properties and allows us to analyse graphs based on their levels of partial balance.

The frustration index is the minimum number of edges whose removal results in a balanced network. Not only computing the frustration index is an NP-hard problem, but finding an approximation for it within any constant factor is believed to be NP-hard. The exact algorithms used in the literature to compute the frustration index are not scalable and cannot process graphs with a few hundred edges.

We formulate computing the frustration index as a graph optimisation problem using binary decision variables associated with graph nodes and edges. We use our first optimisation model to analyse graphs with up to 3000 edges and outperform the state-of-the-art methods in the literature.

Reformulating the optimisation problem, we develop three more efficient  binary linear programming models. Equipping the models with some speed-up techniques allows us to process graphs with 15000 edges on inexpensive hardware. Besides making exact computations possible for large graphs, we show that our computation times are faster by orders of magnitude. On some real-world instances, our algorithm reaches the theoretical limit in terms of effective branching factor.

We extend the concepts of balance and frustration in signed networks to applications beyond the classic friend-enemy interpretation of balance theory in social context. Using a high-performance computer, we analyse graphs with up to 100000 edges to investigate a range of applications from biology and chemistry to finance, international relations, and physics.

Paper 1> 
Paper 2> 
Paper 3>
Paper 4>

 

Biography:

Samin holds a PhD in Computer Science from University of Auckland (New Zealand) and an MSc in Operations Research and Industrial Engineering from Sharif University (Iran). He is currently a research scientist in Lab of Digital and Computational Demography at Max Planck Institute for Demographic Research. His field of interest includes Network Science, Computational Social Science, and Mathematical Modelling.

Wann 11.01.2019
von 16:15 bis 17:45
Wo D 239
Termin übernehmen vCal
iCal