Modularität eines Graphen best < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 10:00 Mo 20.11.2017 | | Autor: | MK234 |
| Aufgabe | Gegeben sei ein ungerichteter Graph mit Knoten a,b,c,d,e und Kanten (a,b), (a,c),(b,c), (d-e) und (c-d).
In diesem Graphen wurden bereits zwei Communities entdeckt. Die erste Communitiy besteht aus den Knoten a,b,c und die zweite aus den Knoten d,e.
Bestimmen Sie die Modularität zu diesem Graphen. |
Die Modularität wird nach folgender Formel bestimmt, mit welcher ich jedoch Probleme habe:
Q = [mm] \summe_{i} [/mm] (e_ii - [mm] a_i^2) [/mm] = Tr e - ||e²||,
Tr e soll die Spur der Matrix sein.
||e|| soll dabei die Summe aller Elemente der Matrix e sein.
Das Netzwerk ist nun in 2 Communities unterteilt. Man definiert eine symmetrische 2x2 Matrix "e" , welche aus Elementen e_ij besteht, d.h. jedes e_ij besteht aus dem Bruchteil der Kanten welche jeweils einen Knoten in Community i und einen Knoten in Community j haben.
[mm] a_i [/mm] = [mm] \summe_{j} [/mm] e_ij, d.h. sie besteht aus der Summe der Zeile oder Spalte der Matrix mit den Elementen welchen den Bruchteil der Kanten bilden welche mit einem Knoten mit Community i verbunden sind.
Die Matrix zu o.g. Formel müßte wie folgt aussehen:
[mm] \pmat{3/5 & 0 \\1/5 & 1/5}.
[/mm]
Wenn ich nun die Formel Q anwende erhalte ich:
Q = (3/5 - (1/5)²) + (1/5 - (1/5)²) = 0.72
Wenn ich jedoch Tr e - ||e²|| anwende erhalte ich:
(3/5 + 1/5) - || (3/5)² + (1/5)² + (1/5)²|| = 4/5 - 0,44 = 0.36.
Was verstehe ich falsch, kann mir jemand weiterhelfen.
Wäre sehr dankbar
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:20 Mi 22.11.2017 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
