Regensburg 2010 – scientific programme
Parts | Days | Selection | Search | Downloads | Help
BP: Fachverband Biologische Physik
BP 24: Networks: From Topology to Dynamics III (joint DY, BP, SOE)
BP 24.1: Talk
Thursday, March 25, 2010, 10:15–10:30, H44
Detection of Mesoscopic Role-Structure in Complex Networks — •Joerg Reichardt1, Roberto Alamino2, and David Saad2 — 1UC Davis, CA — 2Aston University, Birmingham
Not all nodes are created equal in complex networks. Rather, they play diverse roles in the functioning of a network and their role is reflected in the network's link structure. Hence, structural analysis can be used to infer the latent roles and functions of nodes purely based on connectivity data. Currently, network structure is studied at three different levels. At the macro level, global network properties such as degree distributions, path-lengths, diameters or clustering coefficients are investigated. At the micro level, properties of individual nodes and edges such as centrality indices or rank functions such as page-rank are studied. The study of the meso-scale, which aims at studying joint properties of groups of nodes, so far has mainly been focussed on the detection of cohesive subgroups of nodes, so-called communities.
The talk will show that, though important, communities are only one special case of a much wider class of mesoscopic structures called ``stochastic block structures''. This name comes from the fact that latent classes of roles and their resultant patterns of connectivity in a network account for salient block structure in the adjacency matrix of a network when the rows and columns are ordered according to these latent roles.
We present an effective and accurate algorithm that performs this task employing a purely Bayesian approach, show that it outperforms competing approaches and present applications to real world data sets that open new frontiers of research in the study of both structure, function and evolution of complex networks from a mesoscopic perspective.