**Thursday, 14:15 - 14:40 h, Room: H 2013**

**Stefan Wiesberg**

Computing role structures in networks

**Coauthor: Gerhard Reinelt**

**Abstract:**

In network analysis, an established way to obtain structural information is to partition the vertices into so-called regular equivalence classes. In such a partitioning, two nodes *u* and *v* belong to the same class if for every neighbor of *u*, there is a neighbor of *v* in the same class, and vice versa. Thus, for any two classes *C* and *D*, either every or no member of *C* has a neighbor in *D*. The relationships between the classes can hence be visualized by a graph, the so-called role graph. It is of interest in several fields, for example in sociology, economy, or consumer research.

An NP-hard problem in this context is the following one: Given a network *G* and a finite set *R* of role graphs, which element of *R* represents the role structure of *G* in the best possible way? We present one of the first exact algorithms for this problem. It is based on an IP formulation with a quadratic objective function and solved by branch-and-cut. Significant running-time improvements compared to currently used methods are reported.

Talk 3 of the contributed session Thu.2.H 2013

**"Network analysis"** [...]

Cluster 11

**"Integer & mixed-integer programming"** [...]