On the convergence of message passing computation of harmonic influence in social networks

Wilbert Samuel Rossi (Corresponding Author), Paolo Frasca (Corresponding Author)

    Research output: Contribution to journalArticleAcademicpeer-review

    60 Downloads (Pure)

    Abstract

    The harmonic influence is a measure of node influence in social networks that quantifies the ability of a leader node to alter the network's average opinion, acting against an adversary field node. The definition of harmonic influence assumes linear interactions between the nodes described by an undirected weighted graph; its computation is equivalent to solve, for every node, a discrete Dirichlet problem associated to a grounded Laplacian. This measure has been recently studied, under slightly more restrictive assumptions, by Vassio et al., IEEE Trans. Control Netw.Syst., 2014, who proposed a distributed message passing algorithm that concurrently computes the harmonic influence of all nodes. Here, we provide a convergence analysis for this algorithm, which largely extends upon previous results: we prove that the algorithm converges asymptotically, under the only assumption of the interaction Laplacian being symmetric. However, the convergence value does not in general coincide with the harmonic influence: our simulations show that when the network has a larger number of cycles, the algorithm becomes slower and less accurate, but nevertheless provides a useful approximation. Simulations also indicate that the symmetry condition is not necessary for convergence and that performance scales well in the number of nodes of the graph.
    Original languageEnglish
    Number of pages14
    JournalIEEE Transactions on Network Science and Engineering
    DOIs
    Publication statusAccepted/In press - 12 Jan 2018

    Keywords

    • Distributed algorithm
    • Message passing
    • Opinion dynamics
    • Social networks

    Fingerprint Dive into the research topics of 'On the convergence of message passing computation of harmonic influence in social networks'. Together they form a unique fingerprint.

    Cite this