Regensburg 2010 – scientific programme
Parts | Days | Selection | Search | Downloads | Help
SOE: Fachverband Physik sozio-ökonomischer Systeme
SOE 18: Networks: From Topology to Dynamics III (with BP, DY)
SOE 18.2: Talk
Thursday, March 25, 2010, 10:30–10:45, H44
Structuring k-partite networks by decomposition into overlapping communities — •Florian Blöchl1,3, Mara L. Hartsperger1,3, Volker Stümpflen1, and Fabian J. Theis1,2 — 1Institute for Bioinformatics and Systems Biology, Helmholtz Zentrum München — 2Department of Mathematics, TU München — 3Equal contributors
With increasing availability of large-scale networks we face the challenge to interpret these data in a comprehensive fashion. A common solution is a decomposition into modular building blocks, so–called communities. Prominent examples are functional modules in protein interactions. However, the integration of heterogeneous resources results in networks with nodes of multiple colors. Although existing algorithms address this issue, they identify separated, disjoint clusters by assigning each node to exactly one cluster. This is far from reality, where e.g. proteins are commonly part of many complexes or pathways.
We present a novel algorithm for detecting overlapping communities in k-partite graphs. It determines for each node a fuzzy degree-of-membership to each community. Moreover, we additionally estimate a weighted backbone graph connecting the extracted communities. The method is fast and efficient, mimicking the multiplicative update rules employed in algorithms for non-negative matrix factorization.
Results on a disease-gene-protein complex graph show significantly higher homogeneity within the complex and disease clusters than expected by chance. However, the algorithm is readily applicable to other domains with similar problems.