University of Konstanz
Graduiertenkolleg / PhD Program
Computer and Information Science

Graduation Talks


Structural similarity of vertices in networks


Jürgen Lerner, University of Konstanz
Konstanz, Germany

date & place

Wednesday, 22.11.2006, 15:15 h
Room C252


A common task in network analysis is to find groups of vertices that are similar with respect to their structural positions. These methods are aimed to identify vertices that play the same role or have the same function in the network. This thesis examines previous approaches to this problem and proposes a novel concept that unifies and extends established notions and methods. Some previously proposed concepts are built on discrete formulations that are not applicable to empirical data due to instability to noise, computational intractability, and the fact that constraints are only approximately satisfied. Other proposals which yield efficient and stable methods are of limited generality. These methods can only be applied to identify vertices that are close to each other and may fail to recognize global properties of the network. This thesis proposes the concept of structural similarity that is both, general and applicable to noisy irregular data. We can show improvements over previous methods in very different application areas, ranging from network analysis and visualization to combinatorial problems like graph coloring.