Identifying overlapping communities in social networks using multi-scale local information expansion

David Klüner Lukas Ochse Manuel Giel Yannik Korzikowski
RWTH Aachen RWTH Aachen RWTH Aachen RWTH Aachen
david.kluener@rwth-aachen.de lukas.ochse@rwth-aachen.de manuel.giel@rwth-aachen.de yannik.korzikowski@rwth-aachen.de

0 Abstract

Wir stellen mit CLiZZ einen Algorithmus vor, der Communities insbesondere in sozialen Netzwerken erkennt. Im Gegensatz zu vielen gängigen Ansätzen, arbeitet CLiZZ nur mit lokalen Informationen und muss den Gesamtzustand des Netzwerks nicht kennen. CLiZZ ist kein universelles Verfahren sondern fokussiert sich auf die lokalen Verknüpfungen von Knoten, wobei Interaktionen auf verschiedenen Ebenen erkannt werden können. Ein Novum des Algorithmus ist es, die topologische Entropie zu optimieren und einen Vektor für alle Knoten zu errechnen, der die jeweilige Beteiligung an allen Communities beschreibt. Es wird sich zeigen, dass CLiZZ das mit einfachen Berechnungen und folglich niedriger Komplexität schafft. Naturgemäß kann CLiZZ auch sich überschneidende Communities entdecken, da die Zugehörigkeit eines jeden Knotens zu jeder Community klar definiert ist. Durch sein hohes Maß an Genauigkeit und Effizienz ist der Algorithmus prädestiniert, um Communities in echten sozialen Netzwerken zu erkennen.

1 Einleitung

Seit der Veröffentlichung der Arbeit von Barabási und Albert wurden viele komplexe Netzwerke untersucht. Viele Systeme aus unserer Umwelt lassen sich als Graphen darstellen, wobei die Knoten die Einheiten oder Subsysteme und Kanten deren Interaktionen darstellen. Einige dieser Netzwerke wie das Internet[…], Verkehrsnetze[(Xin-Gang Li et al., 2007)], sexuelle Netzwerke und die Verkünüpfung wissenschaftlicher Artikel untereinander[(Newman, Mark E. J. & Girvan, 2004)] tauchen unmittelbar in unserem Alltag auf und ihre Untersuchung ist deshalb von besonderem Interesse. Beispielsweise sind thematisch ähnliche Seiten im Internet stärker untereinander verlinkt als andere und korrelieren mit bestimmten Interessengruppen. Für Suchmaschinen ist es also interessant, diese Subnetze zu identifizieren und in die Such mit einzubeziehen. Mittlerweile wurden schon mehrere Ansätze zur Analyse von Community-Strukturen in Netzwerken entwickelt [(Newman, Mark E. J., 2004), (Newman, Mark E. J. & Girvan, 2004), (Newman, Mark E. J., 2006)]. Unter ihnen hat sich die Modularität \(Q\) als die populärste[(Newman, Mark E. J., 2006), (Danon et al., 2005), (X. S. Zhang et al., 2009)] erwiesen und wird von vielen Forschern untersucht [(Clauset et al., 2004), (Newman, Mark E. J., 2006), (Zhenping Li, Shihua Zhang, Rui-Sheng Wang et al., 2007)]. Die meisten dieser Ansätze erfordern jedoch die Kenntnis des gesamten Netzwerkgraphen, um globale Verbindungen mit Hilfe globaler Informationen zu erkennen. Diese Einschränkung ist für große und komplexe Netzwerke unpraktikabel, denn es ist schwer das gesamte Netzwerk vollständig zu kennen. Darüber hinaus können statistische Methoden nur die größten Gemeinschaftsmuster erkennen und ignorieren dabei ihre mehrstufige Topologie. Somit können sie oft verborgene Gemeinsamkeiten nicht darstellen. Aufgrund dieser Einschränkungen wird in diesem Kapitel ein neuartiger Algorithmus zur Analyse von Netzwerken aufgeführt. Das Ziel des CLiZZ-Algorithmus ist es lokale Informationen, sowie mehrstufige Interaktionsmuster zu erkennen. Er ist kein universeller Ansatz sondern optimiert die topologische Entropie, die die statische Bedeutung eines Netzwerks abbildet. Man bemerkt, dass die topologische Entropiefunktion nicht konvex ist und es ist unrealistisch, von einem optimalen statischen Algorithmus zu erwarten, das globale Minimum zu finden. Darum wurde ein neuartiges dynamisches System entwickelt, das durch einfaches Aktualisieren des Zugehörigkeitsvektors eines jeden Knotens mit geringer Rechenkomplexität auf einem lokalen Minimum konvergiert. Die Anzahl der Gruppen im Netzwerk muss dabei nicht bekannt sein. Der Algorithmus entdeckt mehrstufige Communities, indem er jeden Knoten mit einem Zugehörigkeitsvektor versieht, der die Beteiligung in jeder Community beschreibt. Theoretische Analysen und Experimente zeigen, dass der Algorithmus die Gemeinschaften schnell und präzise erkennen kann.

Dieses Kapitel gliedert sich wie folgt: Im ersten Abschnitt wird das Problem der Gemeinschaftserkennung in sozialen Netzwerken und die Motivation hinter dem Algorithmus erklärt. Im zweiten Abschnitt stellen wir dann den CLiZZ-Algorithmus vor und gehen dabei auf die wichtigsten Eigenschaften des Algorithmus ein. Schließlich schließen wir dieses Kapitel im dritten Abschnitt mit einer Zusammenfassung ab.

1.1 Methodik

Im Folgenden werden einige Begriffe und mathematische Ausdrücke verwendet, die zunächst einer kurzen Erläuterung bedürfen. Ein Netzwerk wird von einem Graphen \(G = (V, E)\) repräsentiert, \(n\) sei dabei die Zahl der Knoten aus \(V\) und \(m\) die Zahl der Kanten aus \(E\). In sozialen Netzwerken gibt es verschiedene Gruppen, die wir im folgenden Communities nennen. Das vorgestellte Verfahren bedingt einer Führungsperson in jeder Community, dem so genannten Leader.

1.2 Motivation

Gegeben sei ein Netzwerk-Graph \(G\). Nun teilt man die Knoten in Communities auf, jede mit einem Leader. Die Leader-Knoten haben zwei Charakteristika; zum einen sind sie mit jedem Knoten ihrer Gruppe verbunden, zum anderen können die Leader untereinander interagieren. Wenn nun der gegebene Algorithmus in jeder Gruppe separat ausgeführt wird, während die Leader auf einer höheren Ebene kommunizieren, können die Knoten schneller angenähert werden. Soziale Netzwerke sind nichts Anderes als Netzwerke mit einer hierarchischen Struktur. In der Rangfolge gibt es Leader-Knoten, welche strukturell wichtiger sind als andere Knoten und daher höher in der Hierarchie angeordnet werden. Nehmen wir das DNS Netzwerk als Beispiel: Im Internet ist der Route-Server als Leader gegeben und steht in der Hierarchie ganz oben. Die Annahme ist, dass das Erkennen dieser Hierarchien auch Aufschluss über die echten Communities gibt. Der Bereich, auf den ein Knoten maximalen Einfluss hat, sollte seine Community sein. CLiZZ soll daher alle natürlichen, bereits gegebenen Leader und deren Einflussbereich finden. Auf diese Art erhält man auch den kürzesten Verbindungsweg zwischen zwei Communities. Gegeben sei ein Graph mit zufällig verteilten Knoten. Diese haben nur lokal begrenztes Wissen über die Struktur. Sie wissen also nichts über die Gesamtstruktur des Netzwerks. Wenn ein Knoten seine eigene Leistung verbessern will, muss er mehr über das gesamte Netzwerk erfahren. Der Knoten kann diese Information dazu nutzen, um seine Nachbarn anzupassen und so seine Leistung zu verbessern. Dieser Vorgang würde aber sehr viel Rechenzeit in Anspruch nehmen. Einen Großteil dieser Rechenzeit entfällt dabei auf Berechnungen mit der Adjazenzmatrix. Da jedem Knoten nur eine begrenzte Menge an Speicher, Energie und Berechnungszeit zugewiesen wird, kann die Adjazenzmatrix nur annäherungsweise genutzt werden. Das Ziel ist es, jeden Knoten mit einem Vektor zu versehen, mit einer kompakten Darstellung über die Verteilung des Graphen und der Position des Knotens unter Berücksichtigung der Nachbarknoten. Es ist wünschenswert, dass dieser Vektor verteilt implementiert wird. Darüber hinaus soll ein Verfahren entwickelt werden, der Strukturen auf verschiedenen Skalen[(Evans & Lambiotte, 2010), (Mucha et al., 2010)] erkennt. Das hat den Vorteil, dass man gleichermaßen grobe Strukturen wie auch verborgene kleine lokale Communities findet. Die meisten klassischen Community-Detection-Verfahren partitionieren den Graph, sodass nur eine Einteilung eines jeden Knoten in eine Community erfolgt. Natürliche Overlapping-Communities werden so nicht erkannt[(Palla et al., 2005), (Li et al., 2012)]. Im Kern der meisten Partitionierungs-Algorithmen entscheidet zumeist eine mathematische Funktion darüber, was eine gute Partition ist. Sobald eine Evaluierungsfunktion definiert wurde, können verschiedene Heuristiken eingesetzt werden, um die optimale Partition zu finden.

2 Der Algorithmus

2.1 Grundlagen

2.1.1 Leadership von Knoten

Der Leadership \(f_{i}\) eines jeden Knoten \(i\) gibt Auskunft darüber, wie einflussreich er im Netzwerk ist und berechnet sich wie folgt:

\[f\left(i\right)=\sum_{j=1;d_{ij}\leq\left\lfloor \frac{3\delta}{\sqrt{2}}\right\rfloor }e^{-\frac{d_{ij} }{\delta}}\]

wobei \(d_{i,j}\) die kürzeste Entfernung zwischen dem Knoten \(i\) und dem Knoten \(j\) ist. \(\delta\in\mathbb{R}_{+}\) ist der Einflussfaktor für den Wirkungsbereich zwischen den Knoten. Schaut man sich den Teil \(e^{-\frac{d_{ij} }{\delta}}\) der Funktion an, so ist der Einflussradius der Knoten zueinander ungefähr \(\left\lfloor \frac{3\delta}{\sqrt{2}}\right\rfloor\). Wenn \(d_{i,j}\) größer als \(\left\lfloor \frac{3\delta}{\sqrt{2}}\right\rfloor\) ist, dann verringert sich der Wert der exponentiellen Funktion schnell auf \(0\). Somit können wir \(\delta\) nutzen, um den Einflussbereich eines Knotens zu kontrollieren und \(f\left(i\right)\) nur für den Bereich \(d_{ij}\leq\left\lfloor \frac{3\delta}{\sqrt{2}}\right\rfloor\) berechnen.
In einem dichten Bereich des Netzwerks haben die Knoten einen höheren Leadership. Sie sind damit Kandidaten für die Rolle als Leader. Knoten mit einem großen Leadership sind wichtiger als jene mit einem geringen Leadership.

2.1.2 Erkennung der Leader-Knoten

Um die Eigenschaften eines komplexen sozialen Netzwerks zu bestimmen, ist es hilfreich, die Leader-Knoten zu ermitteln. Dafür bieten sich unterschiedliche Charakteristika an, wie der Grad eines jeden Knoten oder die Betweenness-Zentralität. Wir benutzen den Leadership, um die Leader-Knoten zu bestimmen. Die Idee hinter dem Konzept einer Community ist, dass es in Neztwerken Bereiche mit einer wesentlich dichteren Vernetzung gibt, also ein regerer Austausch an Informationen stattfindet. Die Communitys sind lokal begrenzt und haben einen Leader, also einen Knoten, der mehr Kanten als alle anderen Knoten in der Community. Die Knoten mit dem geringsten Leadership bilden die Ränder einer Community.
In seltenene Fällen gibt es konkurrierende Leader, die allerdings zu einem zusammengefasst werden können. Sie sind dann gemeinsamer Leader der selben Community. In einem voll verknüpften Graph z.B. gibt es eine Community, in der jeder Knoten auch Leader ist. In einem Ring-Netzwerk hingegen ist ist jeder Knoten Leader seiner eigenen, einelementigen Community.
Insbesondere wenn die Entfernung zweier Leader-Knoten kleiner als \(\left\lfloor \frac{3\delta}{\sqrt{2}}\right\rfloor\) ist, fassen wir sie in einer Community zusammen. Wollen wir die Leader Nodes finden, so verwenden wir eine einfache Breitensuche, ausgehend von einem zufälligen Knoten. Die Komplexität der Operation ist \(\mathcal{O}\left(m\right)\).

2.1.3 Bestimmen der Gruppenzugehörigkeit mittels Random-Walk

Als nächstes stellen wir ein Verfahren vor, dass jedem Knoten einen kleinen Vektor zuordnen, der ihn global einordnet. Ausgehend vom Random-Walk-Verfahen wird dieser Vektor wie folgt definiert.
Gegeben sei ein Graph mit \(a\) Leadern \({l_1},{l_2},...,{l_a}\) und \(n - a\) weiteren Knoten. Bei gegebenen Leadern und deren Einflussreichweite, wird der Mitgliedsvektor eines Knoten \(i\) als \({x_i} = (x_i1,x_i2,...,x_ia) \in {Ra}\) bezeichnet. \(x_ik(t)\) beschreibt den \(k\)-ten Eintrag des Einflussvektors eines Knoten \(i\) zum Zeitpunkt \(t\).
Der Algorithmus arbeitet wie folgt: Als erstes wird der Community-Vektor vom Leader \({l_i}\) als Einheitsvektor festgelegt. Diese \(a\) Vektoren verändern sich nicht. Für reguläre Knoten \(i\) wird \({x_ik}\) zufällig initialisiert, gleichmäßig verteilt mit \([0,1]\) \((k = 1,2,...,a)\). Dann normalisieren wir jede Reihe von \({x_i}\) sodass für alle Leader \(k\) die Summe von \({x_ik}\) 1 ist. Nach jeder Iteration wird der Einflussvektor von jedem Knoten \(i\), der kein Leader ist, mit \((k = 1,2,...,a)\) nach folgender Regel aktualisiert:

\(x_{i}{k}(t+1)=\frac{1}{\sum_{j}a_{ij}+1}\left[x_{i}{k}(t)+\sum\limits_{j}a_{ij}x_{j}{k}(t)\right]\) (2)

wobei \(A=\left\{ a_{ij}\right\}\) die Adjazenzmatrix ist, in welcher \(\left\{ a_{ij}\right\} = 1\) ist, wenn Knoten \(i\) und \(j\) verbunden sind. Sonst gilt \({a_{ij} }\) = 0. Man kann beobachten, dass zu jeder Zeit \(t\), \(\sum_{k}x_{i}{k}\left(t\right)=1\). Gleichung (2) ist äquivalent zu \(X(t + 1) = PX(t) = {(I + D){ - 1} }(A + D)X(t)\), wenn \(P = {(I + D){ - 1} }(A + D)\) eine stochastische Bewegungsmatrix ist. Die Leader beeinflussen das zufällige Ablaufen ausgehend von den anderen Knoten. Es ist wahrscheinlich, dass der Knoten \([i]\) den Leader \([{l_k}]\) trifft, bevor er irgend einen anderen Leader trifft. Mit dem Community-Vektor kann ziemlich genau vorhergesagt werden, zu welcher Community ein Knoten gehört. Auch wenn der Leadership eines Knotens nur lokale Informationen enthält, können wir die Zugehörigkeit zu einer Community mittels zufälligem Ablaufen des ganzen Graphen bestimmen.

2.2 Beschreibung wichtiger Eigenschaften des Algorithmus

In diesem Abschnitt beschreiben wir einige wichtige Eigenschaften des Algorithmus, einschließlich der Berechnung des Einflussfaktors \(\delta\) zur Erkennung von mehrstufigen Communities, zur Identifizierung der Leader mit lokaler Information. Und zur Bestimmung der überlappenden Knoten und zur Schätzung der Komplexität des Algorithmus.

2.2.1 Bestimmen des Einflussfaktors \(\delta\) zur Erkennung von mehrstufigen Communities

Neben der Definition der Leadership wird der Algorithmus nur durch den Einflussfaktor \(\delta\) kontrolliert. Dadurch kann man \(\delta\) nutzen, um die Größe der Communities, die durch den CLiZZ-Algorithmus entdeckt werden, zu bestimmen. An diesem Punkt führen wir die Topologische Entropie \(H\) ein [(Ginestra et al., 2009)]. \(H\) stellt die statistische Signifikante eines Netzwerks dar, um ein passendes \(\delta\) zu bestimmen. Für das Netzwerk \(G = (V,E),V = {v_1},{v_2},...,{v_n}\), bei dem der Leadership von \(V\) \(f(1),f(2),...,f(n)\), ist die Topologische Entropie definiert durch:

\[f(i) = \sum\limits_{j = 1, {d_{ij}} \le \frac{ {3\delta } } { {\sqrt 2 } } }^n { {e^{ - \frac{ { {d_{ij} } } } {\delta } } } }\]

Ein kleines \(H\) sorgt für eine stabile und angemessene Aufteilung. Wenn der Wert von \(\delta\) steigt, sinkt der der Wert von \(H\), bis zu einem optimalen Wert von \(\delta\). An diesem Punkt hat die Entropie ihr Minimum erreicht und steigt darauf wieder bis zu ihren maximalen Wert.

Um dieses optimale \(\delta\) zu finden, wird das Minimum der nichtlineare Funktion \(H(\delta)\) berechnet. Dabei können viele Algorithmen benutzt werden, wie unter anderem der Random-Search-Algorithmus oder der Simulated-Annealing-Algorithmus. Dennoch ist auch ein \(\delta\) zu einem kleinem, aber nicht minimalen Wert von \(H\) bedeutend. Besonders in der Zugehörigkeit der Leadership. Die Einflussreichweite eines Knoten ist nahezu \(\left\lfloor {\frac{ {3\delta } } { {\sqrt 2 } } } \right\rfloor\). Wenn \(0 < \delta < \sqrt 2 /3\) gilt, ist keine Interaktion zwischen zwei Knoten. Die Anzahl der Communities ist \(n\). Gleichzeitig wenn \(\sqrt 2 /3 < \delta < 2\sqrt 2 /3\) gilt, interagiert ein Knoten nur mit seinen Nachbarn. Steigt der Wert von \(\delta\), steigt auch der Einfluss von Knoten und dadurch nimmt die Anzahl der Leader und Communities ab. Zu Schluss, wenn \(\delta \le \sqrt D /3\), \(D\) ist der Durchmesser des Netzwerks, kann jedes Knotenpaar sich gegenseitig beeinflussen egal wie weit sie voneinander entfernt sind.

2.2.2 Bestimmen von Leadern unter Benutzung lokaler Informationen

In diesem Algorithmus kann die Entdeckung von Leadern („Leitern“) einer Community nur durch lokal vorhandene Informationen geschehen. Diese Entdeckung des Leaders liefert sehr viele nützliche Informationen über den wichtigsten Knoten in der betrachteten Community. Die Entfernung eines Leaders einer Community kann zu sehr schwerwiegenden Konsequenzen für die Community führen, wie zum Beispiel ihr zerfallen in mehrere, kleinere Communities. Der Einflussbereich („Community, Hierarchy“) des Leaders ist der Bereich des Netzwerkes, in dem die Meinung des Leaders die einflussreichste ist. Zum Beispiel kann diese Eigenschaft genutzt werden um das Netzwerk gegen epidemische Ausbreitung zu schützen. Aus diesem Grund, kann der Algorithmus die Anzahl der Leaders, welche gleichbedeutend ist mit der Anzahl der Communities, bestimmen. Eine weitere interessante Eigenschaft des Algorithmus’ ist es, neben seiner Fähigkeit automatisch den besten Leader in einem gegebenen Netzwerk zu bestimmen, auch manuell einen Leader auswählen zu können und den Algorithmus, um dieses bestimmten Knoten, Communities konstruieren zu lassen.

2.2.3 Erkennen sich überschneidender Knoten

Es ist wichtig darauf hinzuweisen, dass die große Mehrheit aller Community-Detection-Methoden davon ausgehen, dass die Communities, bestehend aus komplexen Netzwerken, disjunkt sind. Auf Basis dieser Annahme weisen die Algorithmen jeden Knoten lediglich einer, von anderen disjunkten, Gruppe zu. Diese Methoden werden im allgemeinen „Hard-Partitioning-Algorithms“ genannt. In der echten Welt allerdings, überschneiden sich Communities immer zu einem gewissen Grad. Eine wichtige Eigenschaft des CLiZZ-Algorithmus ist es, dass jedem Knoten des Netzwerkes ein Mitglieds-Vektor zugewiesen wird, der die Zugehörigkeit eines Knotens zu jeder Community als eine Prozentzahl darstellt, anstelle eines einfachen Wertes, der binär die Zugehörigkeit zu einer einzelnen Community beschreibt. Als Folge dieser Darstellung, ist es sehr einfach Knoten zu identifizieren, die zu mehr als einer Community gehören und diese werden im allgemeinen als „Overlapping Nodes“ (Li et al., 2012) (Chen et al., 2009) und der CLiZZ Algorithmus als ein „Soft-Partition-Algorithm“ bezeichnet. Der Algorithmus ist zusätzlich in der Lage, Knoten zu identifizieren, welche dem Leader einer Community besonders stark folgen und welche keinen eigenen Leader besitzen, sondern als Verbindungsstück zwischen zwei Communities funktionieren.

2.2.4 Komplexität des Algorithmus

Um die Komplexität des CLiZZ-Algorithmus abzuschätzen, analysiert man zunächst die drei einzelnen Rechenschritte. Der komplexeste Einzelschritt dominiert schließlich die Komplexität des gesamten Algorithmus.
Zunächst wird die Leadership \(f\left(i\right)\) eines jeden Knotens ermittelt. Dazu wird die Exponentialfunktion über die Länge des kürzesten Pfades \(d_{ij}\leq\left\lfloor \frac{3\delta}{\sqrt{2} }\right\rfloor\) zwischen zwei Knoten berechnet. Im günstigsten Fall beträgt die Komplexität der Berechnung \(\mathcal{O}\left(m\right)\), wobei m die Zahl der Verbindungen ist. Im ungünstigsten Fall beträgt die Komplexität \(\mathcal{O}\left(n^{2}\right)\), wie es bei sehr dichten Netzwerken vorkommt.
Nun werden mittels Breitensuche die Knoten mit der höchsten lokalen Leadership gesucht. Dieser Schritt hat die Komplexität von \(\mathcal{O}\left(m\right)\).
Schließlich wird für jeden Knoten ermittelt, welchen Communities er angehört. Dieser Schritt hat ähnlich dem Random-Walk-Verfahren die Komplexität \(\mathcal{O}\left(n\right)\).

Schritt eins, also das berechnen der Leadership, ist die Berechnung mit der höchsten Komplexität. Abhängig vom Grad der Verknüpfung einzelner Knoten ist die Komplexität des CLiZZ-Algorithmus also \(\mathcal{O}\left(m\right)\) im Fall eines schwach verknüpften und \(\mathcal{O}\left(n^{2}\right)\) im Fall eines stark verknüpften Netzwerks.

3 Zusammenfassung

Der CLiZZ-Algorithmus ist ein Ansatz, aufbauend auf lokalen Informationen, Communities in sozialen Netzwerken zu finden. Der Algorithmus ist dabei kein universeller Ansatz sondern konzentriert sich auf die sozialen Interaktionen zwischen Knoten, um die Subnetzwerke zu identifizieren. CLiZZ ermittelt zunächst die Leader und anschließend die zugehörigen Communities unter Verwendung von Random-Walk. Dabei ist die Methode nicht nur dafür geeignet, Communities zu erkennen, sondern auch dazu, Strukturen auf unterschiedlichen Ebenen zu identifizieren. Der Test auf verschiedenen Netzwerken aus echten Anwendungen ergab dabei gute Ergebnisse, die wir in unserer Versuchsanordnung allerdings nicht reproduzieren konnten.

CLiZZ ist also ein neuer OCD-Algorithmus, der nicht nur Communities, sondern auch ihre Hierarchie in komplexen Netzwerken finden kann. Er zeichnet sich insbesondere dadurch aus, relativ gute Ergebnisse lediglich mit lokalen Informationen und wenig Rechenaufwand zu erzielen.

4 Referenzen

  1. Xin-Gang Li, Zi-You Gao, Ke-Ping Li, & Xiao-Mei Zhao. (2007). Relationship between microscopic dynamics in traffic flow and complexity in networks. PHYSICAL REVIEW A, 76(1). https://journals.aps.org/pre/abstract/10.1103/PhysRevE.76.016110
  2. Newman, Mark E. J., & Girvan, M. (2004). Finding and Evaluating Community Structure in Networks. Physical Review, 69(026113).
  3. Newman, Mark E. J. (2004). Fast algorithm for detecting community structure in networks. PHYSICAL REVIEW E, 69(6), 066133. https://doi.org/10.1103/PhysRevE.69.066133
  4. Newman, Mark E. J. (2006). Modularity and Community Structure in Networks. Proceedings of The National Academy of Sciences of the United States of America, 103(23), 8577–8582. https://doi.org/10.1073/pnas.0601602103
  5. Danon, L., Duch, J., Díaz-Guilera, A., & Arenas, A. (2005). Comparing community structure identification. Journal of Statistical Mechanics: Theory and Experiment, P09008. https://doi.org/10.1088/1742-5468/2005/09/P09008
  6. X. S. Zhang, R. S. Wang, Y. Wang, J. Wang, Y. Qiu, L. Wang, & L. Chen. (2009). Modularity optimization in community detection of complex networks. 87(3). http://iopscience.iop.org/article/10.1209/0295-5075/87/38002/meta
  7. Clauset, A., Newman, Mark E. J., & Moore, C. (2004). Finding community structure in very large networks. Phys. Rev., E 70(6).
  8. Newman, Mark E. J. (2006). Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E, 74(3). https://doi.org/10.1103/PhysRevE.74.036104
  9. Zhenping Li, Shihua Zhang, Rui-Sheng Wang, Xiang-Sun Zhang, & Luonan Chen. (2007). Quantitative function for community detection. Physical Review, 77. https://journals.aps.org/pre/abstract/10.1103/PhysRevE.77.036109
  10. Evans, T. S., & Lambiotte, R. (2010). Line graphs of weighted networks for overlapping communities. Eur Phys J B (European Physical Journal B), 77(2), 265–272. https://doi.org/10.1140/epjb/e2010-00261-8
  11. Mucha, P. J., Richardson, T., Macon, K., Porter, M. A., & Onnela, J.-P. (2010). Community Structure in Time-Dependent, Multiscale, and Multiplex Networks. Science, 328(5980), 876–878. https://doi.org/10.1126/science.1184819
  12. Palla, G., Derényi, I., Farkas, I., & Vicsek, T. (2005). Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435(7043), 814–818. https://doi.org/10.1038/nature03607
  13. Li, H.-J., Wang, Y., Wu, L.-Y., Liu, Z.-P., Chen, L., & Zhang, X.-S. (2012). Community structure detection based on Potts model and network’s spectral characterization. EPL, 97(4), 48005. https://doi.org/10.1209/0295-5075/97/48005
  14. Ginestra, B., Pin, P., & Marsili, M. (2009). Assessing the relevance of node features for network structure. Proceedings of The National Academy of Sciences of the United States of America, 106(28), 11433–11438. http://www.pnas.org/content/106/28/11433.abstract
  15. Li, H.-J., Zhang, J., Liu, Z.-P., Chen, L., & Zhang, X.-S. (2012). Identifying overlapping communities in social networks using multi-scale local information expansion. The European Physical Journal B, 85(6). https://doi.org/10.1140/epjb/e2012-30015-5
  16. Chen, D., Fu, Y., & Shang, M. (2009). An Efficient Algorithm for Overlapping Community Detection in Complex Networks. Intelligent Systems, 2009. GCIS ’09. WRI Global Congress On, 1, 244–247. https://doi.org/10.1109/GCIS.2009.68