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


Stefan Wiesberg
Computing role structures in networks

Coauthor: Gerhard Reinelt


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" [...]


  The deal is that Indiana Payday Loans online can save your time, nerves and make a solution of all your financial problems. Since its introduction in the market buying Generic Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.