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.
|Lecture Notes in Computer Science
|Udgivet - 2008
|WAW 2006, Fourth Workshop on Algorithms and Models for the Web-Graph - Banff, Canada
Varighed: 30 nov. 2006 → 1 dec. 2006
Konferencens nummer: 4
|WAW 2006, Fourth Workshop on Algorithms and Models for the Web-Graph
|30/11/2006 → 01/12/2006