Aarhus Universitets segl

English

Du er her: AU » Om AU » Organisation » Communities in Large Networks: Identification and Ranking

Om AU

Communities in Large Networks: Identification and Ranking

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avis › Konferenceartikel › Forskning › peer review

  • Datalogisk Institut
We study the problem of identifying and ranking the members of a community in a very large network with link analysis only, given a set of representatives of the community. We define the concept of a community justified by a formal analysis of a simple model of the evolution of a directed graph. We show that the problem of deciding whether a non trivial community exists is NP complete. Nevertheless, experiments show that a very simple greedy approach can identify members of a community in the Danish part of the web graph with time complexity only dependent on the size of the found community and its immediate surroundings. The members are ranked with a “local” variant of the PageRank algorithm. Results are reported from successful experiments on identifying and ranking Danish Computer Science sites and Danish Chess pages using only a few representatives.
OriginalsprogEngelsk
BogserieLecture Notes in Computer Science
Vol/bind4936
Sider (fra-til)84-96
Antal sider13
ISSN0302-9743
StatusUdgivet - 2008
BegivenhedWAW 2006, Fourth Workshop on Algorithms and Models for the Web-Graph - Banff, Canada
Varighed: 30 nov. 2006 → 1 dec. 2006
Konferencens nummer: 4

Konference

KonferenceWAW 2006, Fourth Workshop on Algorithms and Models for the Web-Graph
Nummer4
LandCanada
ByBanff
Periode30/11/2006 → 01/12/2006

Bibliografisk note

978-3-540-78807-2
Algorithms and Models for the Web-Graph.
Fourth International Workshop, WAW 2006, Banff, Canada, November 30 - December 1, 2006, Revised Papers
Serie: Lecture Notes in Computer Science, Springer
Volumne: 4936

Se relationer på Aarhus Universitet Citationsformater

ID: 7561256