Communities in Large Networks: Identification and Ranking

    Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avisKonferenceartikelForskningpeer review

    Abstract

    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. 20061 dec. 2006
    Konferencens nummer: 4

    Konference

    KonferenceWAW 2006, Fourth Workshop on Algorithms and Models for the Web-Graph
    Nummer4
    Land/OmrådeCanada
    ByBanff
    Periode30/11/200601/12/2006

    Fingeraftryk

    Dyk ned i forskningsemnerne om 'Communities in Large Networks: Identification and Ranking'. Sammen danner de et unikt fingeraftryk.

    Citationsformater