Detection and analysis of overlapping community structures for modelling and prediction in complex networks

Shahriari, Mohsen; Klamma, Ralf; Nejdl, Wolfgang; Jarke, Matthias

doi:HT019751007

Detection and analysis of overlapping community structures for modelling and prediction in complex networks

Shahriari, Mohsen^RWTH*

2018

Verantwortlichkeitsangabevorgelegt von MSc Mohsen Shahriari

ImpressumAachen 2018

Umfang1 Online-Ressource (xii, 217 Seiten) : Illustrationen

Dissertation, RWTH Aachen University, 2018

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Jarke, Matthias (Thesis advisor)^RWTH* ; Klamma, Ralf (Thesis advisor)^RWTH* ; Nejdl, Wolfgang (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2018-07-03

Online
DOI: 10.18154/RWTH-2018-226325
URL: http://publications.rwth-aachen.de/record/729332/files/729332.pdf
URL: http://publications.rwth-aachen.de/record/729332/files/729332.pdf?subformat=pdfa

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Community Mining (frei) ; Community Detection (frei) ; Link Prediction (frei) ; Recommender Systems (frei) ; Expert Identification (frei) ; Cooperation and Defection (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Viele realweltliche Systeme werden als komplexe Netzwerke bezeichnet, die durch Netzwerke interagierender Agenten modelliert werden können. In komplexen Netzwerken können Knoten Mitglieder von dicht verbundenen Komponenten sein, die Community-Strukturen genannt werden und sich locker mit dem Rest des Netzes verbinden. Diese Komponenten können sich überlappend überlagern, hierbei können Knoten Mitglieder mehrerer Communities sein. Viele Beispiele überlappender Communities können im realweltlichen Kontext beobachtet werden. Beispielsweise kann ein Wissenschaftler neben seiner Aktivität in einer wissenschaftlichen Community auch anderen Communities angehören: Familie, Kollegen, Sportvereine, etc. Auch in anderen Netzwerktypen, wie etwa biologischen Netzwerken oder Online Social Networks, finden wir überlappende Community-Strukturen. Überlappende Mitglieder helfen der Community oft dabei zu wachsen und ihr Wissen zu teilen, wie dies etwa anhand der Informationsdiffusion in Lernumgebungen zu beobachten ist. In dieser Dissertation schlagen wir Algorithmen zur Erkennung von überlappenden Communities vor, welche Eigenschaften wie Vermischungsgrad und Informationsdiffusion berücksichtigen. Wir bieten Vorhersagemodelle für die Entwicklung überlappender Communities, außerdem weisen wir die Wichtigkeit von überlappenden Community-Strukturen in der Vorhersage von Mischmustern in Netzwerken nach. Zu diesem Zweck werden überlappende Community-Strukturen verwendet, um Ranglisten- und Empfehlungsmodelle zu generieren. Die von uns vorgeschlagenen Algorithmen übertreffen in vielen Fällen den Stand der Technik und wurden mit unserem WebOCD Software Framework umfassend verfügbar gemacht. Die in dieser Arbeit vorgestellten Algorithmen können in verschiedenen Anwendungsgebieten eingesetzt werden. In diesem Zusammenhang kann man Dynamiken von sich überschneidenden Community-Strukturen nutzen, um Elemente in überfrachteten Informationsräumen zu empfehlen. Darüber hinaus können sich überlappende Community-Strukturen dazu beitragen, den sich überschneidenden Mitgliedern Experten zu empfehlen, um Informationsfluss zu stärken und die Community zu vergrößern. Die Algorithmen, das WebOCD Framework und die Anwendungen wurden für verschiedene Szenarien, darunter auch große informelle Lernnetzwerke im europäischen Learning Layers Projekt, validiert.

Many real-world systems are known as complex networks that can be modeled by networks of interacting agents. In complex networks, vertices can be a member of densely connected components named community structures, which sparsely connect to the rest of the net. Community structures can be overlapping, such that vertices are the member of more than one community. We can see examples of overlapping communities in real life, for instance, a scientist is not only active in scientific communities but also may belong to communities of relatives, family members, colleagues, a sports club, etc. We can also observe overlapping communities in other types of networks, e.g., biological and online social networks. Overlapping members often help communities to scale up and to share their knowledge, e.g., diffusion of information in learning environments. In this dissertation, we propose overlapping community detection algorithms that use properties such as degree mixing and information diffusion. We also build prediction models for the evolution of overlapping communities. Besides, we show the importance of overlapping community structures in the prediction of mixing patterns in networks. For this purpose, dynamics of overlapping community structures are used to propose ranking and recommender models. Our proposed algorithms in many cases outperform state-of-the-art techniques. Moreover, the algorithms have been made widely available in our WebOCD software framework. Different applications can use the algorithms proposed in this thesis. Recommender systems can use overlapping community structure dynamics to recommend items to users in overloaded information spaces. Additionally, overlapping community structures can contribute to recommend overlapping members to experts that this helps to increase the information flow and to scale up communities. Algorithms, WebOCD framework, and applications have been validated in several settings, including large-scale informal Learning networks in the European Learning Layers project.

OpenAccess:
PDF PDF (PDFA)
(additional files)