Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Computing Communities in Large Networks Using Random Walks
verfasst von : Pascal Pons, Matthieu Latapy
Erschienen in: Computer and Information Sciences - ISCIS 2005
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Dense subgraphs of sparse graphs (
communities
), which appear in most real-world complex networks, play an important role in many contexts. Computing them however is generally expensive. We propose here a measure of similarities between vertices based on random walks which has several important advantages: it captures well the community structure in a network, it can be computed efficiently, it works at various scales, and it can be used in an agglomerative algorithm to compute efficiently the community structure of a network. We propose such an algorithm which runs in time
O
(
mn
2
) and space
O
(
n
2
) in the worst case, and in time
O
(
n
2
log
n
) and space
O
(
n
2
) in most real-world cases (
n
and
m
are respectively the number of vertices and edges in the input graph).