Phenomena in growing networks and learning across networks

Abstract

In this dissertation, I study two topics in network science, namely, phenomena in growing networks, and machine learning across networks. The first topic of the dissertation includes the empirical study of different phenomena in real networks at both the microscopic and the macroscopic level, as well as the analytical study of preferential attachment network models. I review existing preferential attachment network models, and give remarks on what exactly the models explain and what can emerge from the models in terms of real-world phenomena at different levels. In the empirical study that follows, I particularly look into two citation networks, and find that (1) the network size grows exponentially over time; (2) the degree growth in citation networks is time-invariant. Existing preferential attachment models cannot explain these two additional phenomena at the same time. I propose a novel analytical framework for a general set of preferential attachment network models, where I connect the growth of the network size and the growth of the node degrees as an eigenproblem. I show that there exist only two solutions to the eigenproblem: Network size growing linearly or exponentially with time. The sometimes lack of solution to the eigenproblem corresponds to the breaking of the system’s time-invariance, which explains the winner-takes-all effect in some model settings, revealing the connection between the Bose-Einstein condensation in the Bianconi-Barabási model and a similar condensation in superlinear preferential attachment. I also show how to estimate the network properties using our framework, for instance the degree distribution and the exponential growth rate of the network. I prove that the ageing effect is necessary to reproduce realistic node degree growth curves, and can prevent the winner-takes-all effect under weak conditions. At last, I use extensive numerical simulations to verify our analytical results, and show that the generated networks have realistic scale-free degree distributions depending on the parameters. In the second topic of the dissertation, I investigate how machine learning techniques, in particular transfer learning, can be applied in real-world networks. Akin to human transfer of experiences from one domain to the next, transfer learning as a subfield of machine learning adapts knowledge acquired in one domain to a new domain. I systematically investigate how the concept of transfer learning may be applied to the study of users on Web platforms, and propose our transfer learning approach, TraNet. TraNet is based on feature transformation from each network’s local feature distribution to a global feature space. I explain our approach in detail with the experiments on the user interaction networks of Wikipedia in different languages. I then show how TraNet is applied to tasks involving the identification of trusted users on Web platforms. I compare the performance of TraNet with other approaches and find that our approach can best transfer knowledge on users across platforms in the given tasks.

In dieser Dissertation untersuche ich zwei Themen der Netzwerkwissenschaft, nämlich Phänomene in wachsenden Netzwerken und netzwerkübergreifendes maschinelles Lernen. Das erste Thema der Dissertation umfasst die empirische Untersuchung verschiedener Phänomene in realen Netzwerken sowohl auf mikroskopischer als auch auf makroskopischer Ebene, sowie die analytische Untersuchung von Preferential Attachment Netzwerkmodellen. Ich überprüfe die bestehende Preferential Attachment Netzwerk-modelle, und gebe Anmerkungen dazu, was genau die Modelle erklären und was sich aus den Modellen in Bezug auf Phänomene der realen Welt auf verschiedenen Ebenen ergeben kann. In der folgenden empirischen Studie untersuche ich insbesondere zwei Zitationsnetzwerke und stelle fest, dass (1) die Netzwerkgröße mit der Zeit exponentiell wächst; (2) der Gradwachstum in Zitationsnetzwerken zeitinvariant ist. Bestehende Preferential Attachment Modelle können diese beiden zusätzlichen Phänomene nicht gleichzeitig erklären. Ich schlage einen neuartigen analytischen Rahmen für einen allgemeinen Satz von Preferential Attachment Netzwerkmodellen vor, wobei ich das Wachstum der Netzwerkgröße und das Gradwachstum als Eigenproblem verbinde. Ich zeige, dass es nur zwei Lösungen für das Eigenproblem gibt: Netzwerkgröße wächst linear oder exponentiell mit der Zeit. Die manchmal fehlende Lösung des Eigenproblems korrespondiert mit dem Aufbrechen der Zeitinvarianz des Systems, was den „Winner-takes-all“ Effekt in einigen Modellsettings erklärt und den Zusammenhang zwischen der Bose-Einstein-Kondensation im Bianconi-Barabási-Modell und einer ähnlichen Kondensation in superlinearer Preferential Attachment aufdeckt. Ich zeige auch, wie man die Netzwerkeigenschaften mit unserem Rahmenwerk schätzen kann, zum Beispiel die Gradverteilung und die exponentielle Wachstumsrate des Netzwerks. Ich beweise, dass der Alterungseffekt notwendig ist, um realistische Gradwachstumskurven zu reproduzieren, und dass er den „Winner-takes-all“ Effekt unter schwachen Bedingungen verhindern kann. Zuletzt verwende ich umfangreiche numerische Simulationen, um unsere analytischen Ergebnisse zu verifizieren, und zeige, dass die generierten Netzwerke realistische skalenfreie Gradverteilungen in Abhängigkeit von den Parametern haben. Im zweiten Thema der Dissertation untersuche ich, wie Techniken des maschinellen Lernens, insbesondere Transfer-Lernens, in Netzwerken der realen Welt angewendet werden können. Ähnlich dem menschlichen Transfer von Erfahrungen von einer Domäne in die nächste, passt Transfer-Lernen als Teilbereich des maschinellen Lernens das in einer Domäne erworbene Wissen an eine neue Domäne an. Ich untersuche systematisch, wie das Konzept des Transfer-Lernens auf die Untersuchung von Benutzern auf Web-Plattformen angewandt werden kann, und schlage unseren Transfer-Lernansatz TraNet vor. TraNet basiert auf der Merkmalstransformation von der lokalen Merkmalsverteilung jedes Netzwerks in einen globalen Merkmalsraum. Ich erläutere unseren Ansatz im Detail anhand der Experimente zu den Benutzerinteraktionsnetzwerken von Wikipedias in verschiedenen Sprachen. Anschließend zeige ich, wie TraNet auf Aufgaben angewendet wird, bei denen es um die Identifizierung von vertrauenswürdigen Benutzern auf Web-Plattformen geht. Ich vergleiche die Leistung von TraNet mit anderen Ansätzen und stelle fest, dass unser Ansatz das Wissen über Benutzer in den gegebenen Aufgaben am besten plattformübergreifend übertragen kann.