Mean-field analysis of the convergence time of message-passing computation of harmonic influence in social networks

W.S. Rossi; P. Frasca

doi:10.1016/j.ifacol.2017.08.435

Mean-field analysis of the convergence time of message-passing computation of harmonic influence in social networks

W.S. Rossi, P. Frasca

University of Twente

Research output: Contribution to journal › Article › Academic › peer-review

1 Citation (Scopus)

131 Downloads (Pure)

Abstract

The concept of harmonic influence has been recently proposed as a metric for the importance of nodes in a social network. A distributed message passing algorithm for its computation has been proposed by Vassio et al. (2014) and proved to converge on general graphs by Rossi and Frasca (2016a). In this paper, we want to evaluate the convergence time of this algorithm by using a mean-field approach. The mean-field dynamics is first introduced in a “homogeneous” setting, where it is exact, then heuristically extended to a non-homogeneous setting. The rigorous analysis of the mean-field dynamics is complemented by numerical examples and simulations that demonstrate the validity of the approach.

Original language	English
Pages (from-to)	2409-2414
Number of pages	6
Journal	IFAC-papersonline
Volume	50
Issue number	1
DOIs	https://doi.org/10.1016/j.ifacol.2017.08.435
Publication status	Published - 1 Jul 2017
Event	20th IFAC World Congress 2017 - Toulouse, France Duration: 9 Jul 2017 → 14 Jul 2017 Conference number: 20 https://www.ifac2017.org/

Keywords

Convergence analysis
Distributed algorithm
Message passing
Nonlinear recursion
Opinion dynamics
Social networks

Access to Document

10.1016/j.ifacol.2017.08.435Licence: CC BY-NC-ND

Cavallo2018nonparametricAccepted author version, 719 KB
Cavallo2018nonparametricFinal published version, 572 KBLicence: CC BY-NC-ND

Cite this

@article{5acc0d8d98f14276b7bc09297d36a508,

title = "Mean-field analysis of the convergence time of message-passing computation of harmonic influence in social networks",

abstract = "The concept of harmonic influence has been recently proposed as a metric for the importance of nodes in a social network. A distributed message passing algorithm for its computation has been proposed by Vassio et al. (2014) and proved to converge on general graphs by Rossi and Frasca (2016a). In this paper, we want to evaluate the convergence time of this algorithm by using a mean-field approach. The mean-field dynamics is first introduced in a “homogeneous” setting, where it is exact, then heuristically extended to a non-homogeneous setting. The rigorous analysis of the mean-field dynamics is complemented by numerical examples and simulations that demonstrate the validity of the approach.",

keywords = "Convergence analysis, Distributed algorithm, Message passing, Nonlinear recursion, Opinion dynamics, Social networks",

author = "W.S. Rossi and P. Frasca",

year = "2017",

month = jul,

day = "1",

doi = "10.1016/j.ifacol.2017.08.435",

language = "English",

volume = "50",

pages = "2409--2414",

journal = "IFAC-papersonline",

issn = "2405-8963",

publisher = "IFAC Secretariat",

number = "1",

note = "20th IFAC World Congress 2017 ; Conference date: 09-07-2017 Through 14-07-2017",

url = "https://www.ifac2017.org/",

}

TY - JOUR

T1 - Mean-field analysis of the convergence time of message-passing computation of harmonic influence in social networks

AU - Rossi, W.S.

AU - Frasca, P.

N1 - Conference code: 20

PY - 2017/7/1

Y1 - 2017/7/1

N2 - The concept of harmonic influence has been recently proposed as a metric for the importance of nodes in a social network. A distributed message passing algorithm for its computation has been proposed by Vassio et al. (2014) and proved to converge on general graphs by Rossi and Frasca (2016a). In this paper, we want to evaluate the convergence time of this algorithm by using a mean-field approach. The mean-field dynamics is first introduced in a “homogeneous” setting, where it is exact, then heuristically extended to a non-homogeneous setting. The rigorous analysis of the mean-field dynamics is complemented by numerical examples and simulations that demonstrate the validity of the approach.

AB - The concept of harmonic influence has been recently proposed as a metric for the importance of nodes in a social network. A distributed message passing algorithm for its computation has been proposed by Vassio et al. (2014) and proved to converge on general graphs by Rossi and Frasca (2016a). In this paper, we want to evaluate the convergence time of this algorithm by using a mean-field approach. The mean-field dynamics is first introduced in a “homogeneous” setting, where it is exact, then heuristically extended to a non-homogeneous setting. The rigorous analysis of the mean-field dynamics is complemented by numerical examples and simulations that demonstrate the validity of the approach.

KW - Convergence analysis

KW - Distributed algorithm

KW - Message passing

KW - Nonlinear recursion

KW - Opinion dynamics

KW - Social networks

UR - http://www.scopus.com/inward/record.url?scp=85031817662&partnerID=8YFLogxK

U2 - 10.1016/j.ifacol.2017.08.435

DO - 10.1016/j.ifacol.2017.08.435

M3 - Article

AN - SCOPUS:85031817662

SN - 2405-8963

VL - 50

SP - 2409

EP - 2414

JO - IFAC-papersonline

JF - IFAC-papersonline

IS - 1

T2 - 20th IFAC World Congress 2017

Y2 - 9 July 2017 through 14 July 2017

ER -

Mean-field analysis of the convergence time of message-passing computation of harmonic influence in social networks

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this