PUB - Publikationen an der Universität Bielefeld

This dissertation combines different viewpoints on the emerging "physics of networks". After a general introduction to the new physics of complex networks (scale-free degree distribution, small worlds, etc.), and ethical considerations about the protection of data about people, three different aspects of and on complex networks are presented, each of which formed the topic of a paper. In the first paper, the network of EU-funded collaborative R&D projects is analyzed by measuring the "small world" effects of small diameter and high clustering. Scale-free degree distributions are found, and the exponents measured. The results are similiar to other collaboration networks. Three plausible models (random set, configuration model similiar to MolloyReed, and an additive version of the latter) are created and examined to understand the influence of the size distributions of projects and organisations. While many of the empirical findings are similiar to the "synthetic Europes", the main found difference is higher edge multiplicities of the unimodal projections in the case of the empirical Europe, implying that previous collaborations are repeated more often than in the respective random models. The second paper uses the example of corruption to illustrate how one can extend classical epidemic processes to generalized epidemic processes (GEP) on complex networks. There is a strong nonlinear dependence of the transmission probability on the local density of corruption: To model the resistance of the individual against corruption, the main neighbour infection process is triggered only above a given threshold of infected neighbours. The model also includes a global mean-field influence that simulates the effect of e.g. mass media, and a similiarly global cleaning process that depends on the ratio of the still uncorrupted nodes. The local and global processes can exhibit a fatal resonance. In contrast to classical epidemics, a phase transition in the initial infection ratio is observed, and studied under variation of the process and the network parameters. A smart transition finder algorithm is used to avoid critical slowing down in the critical region. The networks are varied with respect to edge density, triangle density, exponent of the scale-free degree distribution, and degree correlation (additive, multiplicative). High clustering accelerates the infection in this model. Scale-free networks with exponent gamma approaching 2 (resulting in hubs with a very large degree) exhibit an interesting difference: Such model societies with a multiplicative degree correlation are easier to completely infect by our corruption process than networks with an additive degree correlation. The third paper describes a clustering approach that seems to be new to the physics networks community. Clustering results are often visualized as block-structured adjacency matrices. When the nodes are clustered and sorted by their cluster order, the adjacency matrix shows blocks of more-strongly connected subspaces along the matrix diagonal. The following idea inspired this new algorithm was: Why not directly sort the nodes into such a block-structure? An inductively developed deterministic algorithm is described that uses a parameterized heuristic of mutual distances of all nodes, reorders them by smallest distances in a linear chain, cuts between clusters at the highest distance jumps, and takes the one clustering with the best modularity as the end result. The three parameters influence the mixing of the direct connection weight A_ij, the two-step connections (A^2)_ij, the N1-neighbourhood similarity, and the N2-neighbourhood similarity (structural equivalence). A proof-of-concept-implementation suitable for small networks is described. The algorithmic time complexity is O(N^3) due to the matrix multiplication; a discussion of possible enhancements to the algorithm is given. The success of the algorithm is demonstrated through application to several networks: the Zachary Karate Club, where by this method a 3-clustering could be found that has a higher-modularity than the clusterings reported in the literature; a set of 96 tumors that are clustered by their gene-similarity; and clustered topics of 27000 EU-funded R&D projects.