Power walk : revisiting the random surfer

    Research output: Chapter in Book / Conference PaperConference Paperpeer-review

    2 Citations (Scopus)

    Abstract

    ![CDATA[Measurement of graph centrality provides us with an indication of the importance or popularity of each vertex in a graph. When dealing with graphs that are not centrally controlled (such as the Web, social networks and academic citation graphs), centrality measure must 1) correlate with vertex importance/popularity, 2) scale well in terms of computation, and 3) be difficult to manipulate by individuals. The Random Surfer probability transition model, combined with Eigenvalue Centrality produced PageRank, which has shown to satisfy the required properties. Existing centrality measures (including PageRank) make the assumption that all directed edges are positive, implying an endorsement. Recent work on sentiment analysis has shown that this assumption is not valid. In this article, we introduce a new method of transitioning a graph, called Power Walk, that can successfully compute centrality scores for graphs with real weighted edges. We show that it satisfies the desired properties, and that its computation time and centrality ranking is similar to when using the Random Surfer model for non-negative matrices. Finally, stability and convergence analysis shows us that both stability and convergence when using the power method, are dependent on the Power Walk parameter β.]]
    Original languageEnglish
    Title of host publicationProceedings of the 18th Australasian Document Computing Symposium (ADCS 2013), Brisbane, Queensland, December 5â€Â�6, 2013
    PublisherACM
    Pages50-57
    Number of pages8
    ISBN (Print)9781450325240
    DOIs
    Publication statusPublished - 2013
    EventAustralasian Document Computing Symposium -
    Duration: 5 Dec 2013 → …

    Conference

    ConferenceAustralasian Document Computing Symposium
    Period5/12/13 → …

    Fingerprint

    Dive into the research topics of 'Power walk : revisiting the random surfer'. Together they form a unique fingerprint.

    Cite this