Complex Network Analysis

Local Identification of Central Nodes, Clusters, and Network Motifs in Very Large Complex Networks (DFG SPP 1736)

The analysis of complex networks relies mostly on three different approaches: the identification of central nodes, the assignment of nodes to one or more groups of topologically similar other nodes, so-called clusters, and the identification of subgraphs occurring more often than expected by chance. Behind all of these approaches there are at least a dozen functions and measures to instantiate them, which all follow the same logic, which is, however, not always clearly defined. All of these approaches are today based on methods that make use of global properties of the graph like the distance between all pairs of nodes (O(nm+n^2 log n)), global ranking of similar node or edge pairs (O(n^2), or the comparison with random graph models of the same structure as the observed one (O(m log m)). Thus, none of these fundamental approaches can be directly transferred to the analysis of very large complex networks as needed today.
In this project, we will develop a model of local versions of these three approaches, which fundamentally describes how a corresponding measure can be transformed into a local variant of itself. The basic method is to develop algorithms based on graph theoretical reasoning where the algorithm engineering is informed by machine learning to include real-world properties of the data and real-life behavior of hardware. The newly developed measures and models will be put into praxis and their usefullness will be evaluated on big data of RIOT games, a USA-based computer game company.

Selected Publications

Press Coverage

One plus one makes three for social networks

In this cooperation with Michael Hanselmann and Fred Hamprecht we explored how much a typical social network platform (like Facebook) can infer about relationships between non-members. Based on the information of who knows whom on the platform and a list of contacts to non-members we estimate that a platform like facebook can infer about 40% of the connections between non-members.

Selected Publications

Press Coverage