Aarhus Universitets segl

Communities in Large Networks: Identification and Ranking

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avisKonferenceartikelForskningpeer 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.
BogserieLecture Notes in Computer Science
Sider (fra-til)84-96
Antal sider13
StatusUdgivet - 2008
BegivenhedWAW 2006, Fourth Workshop on Algorithms and Models for the Web-Graph - Banff, Canada
Varighed: 30 nov. 20061 dec. 2006
Konferencens nummer: 4


KonferenceWAW 2006, Fourth Workshop on Algorithms and Models for the Web-Graph

Bibliografisk note

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