Staff:Prof. Dr. Katharina A. Zweig, Technische Universität Kaiserslautern |
|
Description:
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.