Eine kritische Analyse von Vernetzungsmaßen in sozialen Netzwerken

Durch das immense Wachstum von Web-basierten Diensten wie z. B. facebook.com gewinnt das Thema soziale Netzwerke gegenwärtig zunehmend an Bedeutung. Eine zentrale Herausforderung – u. a. für die erfolgreiche Umsetzung zahlreicher betriebswirtschaftlicher Maßnahmen wie z. B. Virales Marketing – stellt dabei die Identifikation derjenigen Schlüsselpersonen dar, die strukturell besonders gut in ein soziales Netzwerk eingebunden sind. Hierfür wurde in der Social Network Analysis eine Vielzahl von Maßen zur Quantifizierung der Vernetzung der einzelnen Akteure eines sozialen Netzwerks entwickelt. Vor diesem Hintergrund wird im vorliegenden Beitrag der aktuelle Stand der Forschung im Hinblick auf Vernetzungsmaße in sozialen Netzwerken aufgezeigt. Angesichts stark variierender Erkenntnisse zur Güte verschiedener Vernetzungsmaße verfolgt der Beitrag zudem das Ziel, die enorme Relevanz einer reflektierten Anwendung der existierenden Vernetzungsmaße zu illustrieren. Hierfür werden fünf der in der Social Network Analysis am häufigsten diskutierten Vernetzungsmaße anhand von drei einfachen allgemeinen Eigenschaften im Hinblick auf das Verhalten von Vernetzungsmaßen analysiert.

Social networks are currently gaining increasing impact in the light of the ongoing growth of web-based services like facebook.com. One major challenge for the economically successful implementation of selected management activities such as viral marketing is the identification of key persons with an outstanding structural position within the network. For this purpose, social network analysis provides a lot of measures for quantifying a member’s interconnectedness within social networks. In this context, our paper shows the state of the art with regard to centrality measures for social networks. Due to strongly differing results with respect to the quality of different centrality measures, this paper also aims at illustrating the tremendous importance of a reflected utilization of existing centrality measures. For this purpose, the paper analyzes five centrality measures commonly discussed in literature on the basis of three simple requirements for the behavior of centrality measures.

1. Genügt statt einer exakten Berechnung die Approximation der Werte der BC, so kann auf den noch schnelleren Algorithmus von Bader et al. (2007) zurückgegriffen werden.

2. Ein Automorphismus ist ein Isomorphismus von einem Graphen auf sich selbst, wobei zwei Graphen G=(V _G ,E _G ) und G′=(V _G′,E _G′) isomorph genannt werden, wenn eine bijektive Abbildung η:V _G →V _G′ mit (a,b)∈E _G genau dann, wenn (η(a),η(b))∈E _G′ für alle a,b∈V _G existiert.

3. Eine Ausnahme bildet der Fall, dass die neue Kante (x,y) hinzugefügt wird und sich dadurch d _G′(x,y)=1 ergibt.

4. Als nichtnegative, irreduzible Matrix besitzt A stets einen positiven Eigenwert, der gleich dem Spektralradius ist und zu dem ein Eigenvektor mit positiven Einträgen existiert (Graham 1987, S. 131).

5. Für ausführliche Berechnungen und weitere Ausführungen vgl. Anhang A.

6. Im Gegensatz zur Arbeit von Katz wird auf die Normierung der Spaltensumme der Adjazenzmatrix durch Multiplikation mit 1/(n−1) verzichtet. Das Ergebnis weicht dadurch um eine multiplikative Konstante von dem Ergebnis in der Originalarbeit von Katz ab. Zudem unterscheidet sich das VM von Katz im Rahmen der beschriebenen Annahmen lediglich durch eine Konstante von der Alpha-Zentralität. Weitere Ausführungen hierzu sind Anhang B zu entnehmen.

7. Für detaillierte Ausführungen vgl. Anhang C.

Authors and Affiliations

1. FIM Kernkompetenzzentrum Finanz- & Informationsmanagement, Universität Augsburg, Universitätsstraße 12, 86159, Augsburg, Deutschland

   Andrea Landherr,  Bettina Friedl &  Julia Heidemann

Corresponding author

Correspondence to Andrea Landherr.

Angenommen nach zwei Überarbeitungen durch Prof. Dr. Buxmann.

This article is also available in English via http://www.springerlink.com and http://www.bise-journal.org: Landherr A, Friedl B, Heidemann J (2010) A Critical Review of Centrality Measures in Social Networks. Bus Inf Syst Eng. doi: 10.1007/s12599-010-0127-3.

Anhang A: Gegenbeispiele zu den Eigenschaften 1 bis 3 bei der Eigenvektorzentralität

Im Folgenden werden die Berechnungen im Zusammenhang mit den Gegenbeispielen zu den Eigenschaften 1 bis 3 bei Anwendung der EC ausführlich dargestellt. Die Berechnungen wurden dabei mittels der Software Octave vorgenommen.

1.1 A.1 Gegenbeispiel zu Eigenschaft 1

Die folgenden Berechnungen beziehen sich auf das Netzwerk 6a. Zunächst wird die Adjazenzmatrix A des Ausgangsnetzwerks (vor Hinzufügen der Beziehung (4,6)) bestimmt. Für diese Matrix werden der maximale Eigenwert sowie ein zugehöriger Eigenvektor berechnet.

Im nächsten Schritt wird das Netzwerk dahingehend modifiziert, dass eine neue Beziehung zwischen den Akteuren 4 und 6 hinzugefügt wird. Dadurch ergibt sich folgende modifizierte Adjazenzmatrix A′, für welche der maximale Eigenwert und ein zugehöriger Eigenvektor berechnet werden:

Für Akteur 1 ergibt sich dabei zunächst der Wert \(\sigma_{E}^{G}(1)=0{,}602\) und nach Hinzufügen der Beziehung (4,6) der Wert \(\sigma_{E}^{G'}(1)=0{,}417\), obwohl sich die Distanz des Akteurs 1 zu Akteur 6 verringert hat. Dies verletzt Eigenschaft 1.

1.2 A.2 Gegenbeispiel zu Eigenschaft 2

Für Netzwerk 6b wird zunächst ebenfalls die zugehörige Adjazenzmatrix A des Ausgangsnetzwerks (vor Hinzufügen der Beziehung (1,2)) bestimmt und der maximale Eigenwert sowie ein zugehöriger Eigenvektor berechnet.

Nach Hinzufügen der Beziehung (1,2) ergibt sich die folgende modifizierte Adjazenzmatrix A′, für welche der maximale Eigenwert und ein zugehöriger Eigenvektor berechnet werden:

Für Akteur 4 ergibt sich dabei zunächst der Wert \(\sigma_{E}^{G}(4)=0{,}604\) und nach Hinzufügen der Beziehung (1,2) der Wert \(\sigma_{E}^{G'}(4)=0{,}530\), obwohl sich der Kontakt des Akteurs 4 zu Akteur 2 durch die neue Beziehung (1,2) intensiviert hat. Dies verletzt Eigenschaft 2.

1.3 A.3 Gegenbeispiel zu Eigenschaft 3

Für Netzwerk 6c wird zunächst ebenfalls die zugehörige Adjazenzmatrix A des Ausgangsnetzwerks (vor Hinzufügen der Beziehung (4,6)) bestimmt und der maximale Eigenwert sowie ein zugehöriger Eigenvektor berechnet.

Nach Hinzufügen der Beziehung (4,6) ergibt sich die folgende modifizierte Adjazenzmatrix A′, für welche der maximale Eigenwert und ein zugehöriger Eigenvektor berechnet werden:

Während vor Hinzufügen der Beziehung (4,6) Akteur 4 eine geringere Vernetzung aufweist als Akteur 6 (\(\sigma_{E}^{G}(4)=0{,}271<\sigma_{E}^{G}(6)=0{,}311)\), ändert sich aufgrund der hinzugefügten Beziehung die Rangfolge der beiden Akteure (\(\sigma_{E}^{G'}(4)=0{,}435>\sigma_{E}^{G'}(6)=0{,}421)\), was einen Widerspruch zu Eigenschaft 3 darstellt.

Die Berechnungen belegen überdies, dass die Eigenschaften 1 bis 3 auch dann oftmals nicht erfüllt sind, wenn man den jeweiligen Eintrag des Eigenvektors mit dem maximalen Eigenwert λ _max(A) bzw. λ _max(A′) der jeweiligen Adjazenzmatrix multipliziert, der sich durch das Hinzufügen der neuen Beziehung erhöhen kann, jedoch keinesfalls niedriger wird (Bermann und Plemmons 1994).

Anhang B: Alpha-Zentralität

Im Rahmen der beschriebenen Annahmen unterscheidet sich das VM von Katz lediglich durch eine Konstante von der Alpha-Zentralität (AC) σ _α , die als

definiert ist. Dabei repräsentiert I _n die Einheitsmatrix der Dimension n und A die Adjazenzmatrix des Netzwerks aus Beziehungen zwischen den Akteuren des betrachteten Netzwerks. Der Vektor c ermöglicht zudem die Berücksichtigung der von der Beziehungsstruktur unabhängigen Einflüsse auf die Vernetzung. Der Parameter α gibt die relative Gewichtung der beziehungsinduzierten gegenüber den exogenen Einflüssen auf die Vernetzung an (Bonacich und Lloyd 2001). Unterscheiden sich die exogenen Einflüsse nicht, so kann c=1 gewählt werden. Bei α=k unterscheiden sich die Werte der AC und des VM von Katz folglich nur um die Konstante 1. Die Aussagen der Analysen zum VM von Katz in Abschn. 4.5 gelten deshalb ebenso für die AC. Um Redundanzen zu vermeiden, wurde auf die separate Darstellung der AC verzichtet.

Anhang C: Ausführungen zur Gültigkeit der Eigenschaft 3 beim VM von Katz

3.1 C.1 Beschreibung der Simulation

Die Überprüfung, ob beim VM von Katz Eigenschaft 3 erfüllt ist, war analytisch nicht allgemein möglich. Daher simulierten die Autoren zusammenhängende Netzwerke mit 5 bis 1000 Knoten und untersuchten die Auswirkung des Hinzufügens einer Kante (x,y) auf die Rangfolge zweier zuvor nicht verbundener Knoten x und y. Da sich bei Durchführung von ca. 1 Million Versuchen die Rangfolge der neu verbundenen Knoten anhand ihrer Vernetzung nicht änderte, ist davon auszugehen, dass Eigenschaft 3 beim VM von Katz generell erfüllt ist.

Die Netzwerke und deren Modifikationen wurden dabei nach folgendem Vorgehen erzeugt: Zunächst wird eine zufällige Binärmatrix B erzeugt. Da die Adjazenzmatrix des sozialen Netzwerks aufgrund der Symmetrie der Beziehungen symmetrisch sein muss, wird der obere Dreiecksteil der Matrix B nach unten gespiegelt und man erhält die symmetrische Matrix A. In einem nächsten Schritt werden all die Matrizen verworfen, die isolierte Knoten enthalten (mindesten eine Zeilen- bzw. Spaltensumme <1) und damit offensichtlich keine zusammenhängenden Graphenrepräsentieren. Für die verbleibenden Matrizen wird wie folgt vorgegangen: zunächst wird dieAdjazenzmatrix A′ zu einem modifizierte Netzwerk berechnet, indem ein Eintrag mit a _xy =0 identifiziert wird und a′ _xy =1 sowie a′ _yx =1 gesetzt wird, d. h. im Graphen wird eine neue Kante (x,y) hinzugefügt. Im Anschluss wird sowohl für die Matrix A als auch für die Matrix A′ das VM von Katz für die Knoten x und y berechnet und die Rangfolge der beiden Knoten vor und nach Modifikation des Netzwerks ermittelt. Die Autoren gehen aufgrund der beschriebenen Simulationsstudie davon aus, dass Eigenschaft 3 beim VM von Katz erfüllt ist.

3.2 C.2 Teilweise analytischer Nachweis

Für einige Spezialfälle ist ein analytischer Nachweis, dass die Eigenschaft 3 beim VM von Katz erfüllt ist, möglich. Daher werden im Folgenden für diese Fälle, d. h. unter bestimmten einschränkenden Annahmen, formale Beweise zur Gültigkeit von Eigenschaft 3 näher ausgeführt. Bei der Betrachtung wird die Konstante −1, die aufgrund der Subtraktion der Einheitsmatrix in Formel (5′) hinzukommen würde, nicht berücksichtigt, da diese bei der Differenzbildung im Zusammenhang mit dem Vergleich der Rangfolge wegfällt.

Für die weiteren Ausführungen werden folgende Bezeichnungen verwendet:

und \(\tilde{B}=(I_{n}-kA-kE^{xy})^{-1}=(\tilde{B}_{ij})\), wobei \(E^{xy}=(E_{ij}^{xy})\) die Matrix beschreibt deren Einträge – bis auf die beiden Einträge \(E_{xy}^{xy}\) und \(E_{yx}^{xy}\) – null sind. Die Einträge \(E_{xy}^{xy}\) und \(E_{yx}^{xy}\) haben den Wert 1 und bilden somit die hinzukommende Kante (x,y) ab.

Nach Sherman und Morrison (1950) erhält man mit obigen Bezeichnungen bei zweimaliger Anwendung der Formel zur Berechnung der Inversen einer Matrix bei Änderung jeweils eines Matrixeintrags (durch das Hinzufügen der Kante (x,y) ändern sich die Einträge an den Positionen a _xy und a _yx ) den folgenden Ausdruck für die Elemente der Matrix \(\tilde{B}_{ij}\):

Für \(\sigma_{K}^{G'}(x)=\sum_{i=1}^{n}\tilde{B}_{ix}\) bzw. \(\sigma_{K}^{G'}(y)=\sum_{i=1}^{n}\tilde{B}_{iy}\) ergibt sich somit:

bzw.

Die Differenz der Vernetzung von x und y im Graphen G′, der durch Hinzufügen der Kante (x,y) entsteht, beträgt folglich:

Der Nenner dieses Ausdrucks wird im Folgenden mit N:=(1−kb _xy )²−k ² b _xx b _yy abgekürzt.

Dabei ist b _xx −1≥0. Dies ist damit zu begründen, dass b _xx −1 die nach ihrer Weglänge gewichtete Anzahl von Wegen in G, die in x beginnen und enden, repräsentiert. Da dieser Wert bei einem zusammenhängenden Graphen immer positiv ist, ist b _xx −1≥0 und damit auch b _xx >0. Analog folgt b _yy >0.

Eigenschaft 3 umfasst zwei Aussagen. Teilaussage 1 bezieht sich auf die Rangfolge zweier Knoten, die zunächst eine unterschiedliche Vernetzung haben. Der zweite Teil von Eigenschaft 3 trifft eine Aussage für Knoten, denen das VM im ursprünglichen Graphen die gleiche Vernetzung attestiert. Die beiden Teilaussagen werden im Folgenden getrennt voneinander für einige Spezialfälle bewiesen.

Teilaussage 1

z. z.:

Die vier Fälle, in denen Teilaussage 1 von Eigenschaft 3 beim VM von Katz in jedem Fall erfüllt ist, werden im Folgenden näher ausgeführt:

(a) Annahmen: b _xx >b _yy und

1−kb _xy −kb _xx >0

Aus den beiden Annahmen folgt, dass 1−kb _xy −kb _yy >0.

(b) Annahmen: b _xx >b _yy und

1−kb _xy −kb _xx =0

Aus den beiden Annahmen folgt

1−kb _xy =kb _xx >0 (da k,b _xx >0)

(c) Annahmen: b _xx =b _yy und

1−kb _xy >kb _xx

(d) Annahmen: b _xx =b _yy ,

1−kb _xy <kb _xx und |1−kb _xy |<kb _xx

Zusammenfassend kann die Gültigkeit der Teilaussage 1 von Eigenschaft 3 beim VM von Katz bewiesen werden, falls entweder

(1) b _xx >b _yy und 1−kb _xy −kb _xx ≥0 oder (2) b _xx =b _yy sowie 1−kb _xy >kb _xx bzw. 1−kb _xy <kb _xx und |1−kb _xy |<kb _xx gilt.

Teilaussage 2

z. z.:

Annahmen: b _xx =b _yy und

|1−kb _xy |≠kb _xx

Unter den Bedingungen b _xx =b _yy und |1−kb _xy |≠kb _xx ist die zweite Teilaussage von Eigenschaft 3 beim VM von Katz ebenfalls erfüllt.

Reprints and permissions