[Graphen] Algorithmen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Algorithmen implementieren. |
Servus,
ich moechte einen ungerichteten, ungewichteten Graphen untersuchen.
(~1 Mio Knoten & ~10 Mio Kanten)
Dazu moechte in Java Algorithmen implementieren fuer
[mm] \circ [/mm] betweenness centrality
[mm] \circ [/mm] clustering coefficients
[mm] \circ [/mm] degree distribution
Ich habe nun per google auch die eine oder andere Seite gefunden,
die diese Parameter erklaert.
![[]](/images/popup.gif) z.B. hier
Was ich nun suche waere ein Buch, Homepage usw. in der die
Umsetzung/Programmierung der Algorithmen fuer diese Kenngroessen
verstaendlich erklaert werden.
Gruss
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:04 Sa 20.05.2006 | | Autor: | Frank05 |
> Algorithmen implementieren.
> Servus,
>
> ich moechte einen ungerichteten, ungewichteten Graphen
> untersuchen.
> (~1 Mio Knoten & ~10 Mio Kanten)
>
> Dazu moechte in Java Algorithmen implementieren fuer
>
> [mm]\circ[/mm] clustering coefficients
> Ich habe nun per google auch die eine oder andere Seite
> gefunden,
> die diese Parameter erklaert.
> z.B. hier
Ich hab die Begriffe noch nicht gehört, aber auf der Seite kommt mir die Anzahl der Tripel etwas komisch vor. Im Beispiel mit den Knoten von i-k hat i 5 Tripel, im Beispiel mit den Knoten von 1-5 hat 3 aber 6 Tripel (obwohl einen Nachbarn weniger).. ich dachte ein Tripel wäre lediglich eine Menge mit 3 Knoten a,b,c, so dass {a,b} und {b,c} in der Kantenmenge sind ?
Sollte ein Tripel so definiert sein, dann bekommst du die Anzahl der Tripel ganz einfach als [mm]({deg(v) \atop 2})[/mm].
Das größere Problem dürfte aber das Zählen der Dreiecke sein. Hier bietet es sich eventuell an einen Blick auf wikipedia zu werfen, da dort eine äquivalente Formel hergeleitet wird, die einfacher zu berechnen ist.
hth,
Frank
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:56 Mo 19.06.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
