Efficiency of Algorithms for Computing Influence and Information Spreading on Social Networks

Vesa Kuikka; Henrik Aalto; Matias Ijäs; Kimmo K. Kaski

doi:10.3390/a15080262

Efficiency of Algorithms for Computing Influence and Information Spreading on Social Networks

Vesa Kuikka^*, Henrik Aalto, Matias Ijäs, Kimmo K. Kaski

^*Corresponding author for this work

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

8 Citations (Scopus)

108 Downloads (Pure)

Abstract

Modelling interactions on complex networks needs efficient algorithms for describing processes on a detailed level in the network structure. This kind of modelling enables more realistic applications of spreading processes, network metrics, and analyses of communities. However, different real-world processes may impose requirements for implementations and their efficiency. We discuss different transmission and spreading processes and their interrelations. Two pseudo-algorithms are presented, one for the complex contagion spreading mechanism using non-self-avoiding paths in the modelling, and one for simple contagion processes using self-avoiding paths in the modelling. The first algorithm is an efficient implementation that can be used for describing social interaction in a social network structure. The second algorithm is a less efficient implementation for describing specific forms of information transmission and epidemic spreading.

Original language	English
Article number	262
Pages (from-to)	1-15
Number of pages	15
Journal	Algorithms
Volume	15
Issue number	8
DOIs	https://doi.org/10.3390/a15080262
Publication status	Published - Aug 2022
MoE publication type	A1 Journal article-refereed

Keywords

centrality measures
community detection
epidemic spreading
influence spreading
information spreading
modelling social networks
pseudo-algorithm
scalable algorithm
social media networks
social networks

Access to Document

10.3390/a15080262Licence: CC BY

Efficiency of Algorithms for Computing Influence and Information Spreading on Social NetworksFinal published version, 307 KBLicence: CC BY

Cite this

@article{c118231218b44b7b9aa46f070dade1d3,

title = "Efficiency of Algorithms for Computing Influence and Information Spreading on Social Networks",

abstract = "Modelling interactions on complex networks needs efficient algorithms for describing processes on a detailed level in the network structure. This kind of modelling enables more realistic applications of spreading processes, network metrics, and analyses of communities. However, different real-world processes may impose requirements for implementations and their efficiency. We discuss different transmission and spreading processes and their interrelations. Two pseudo-algorithms are presented, one for the complex contagion spreading mechanism using non-self-avoiding paths in the modelling, and one for simple contagion processes using self-avoiding paths in the modelling. The first algorithm is an efficient implementation that can be used for describing social interaction in a social network structure. The second algorithm is a less efficient implementation for describing specific forms of information transmission and epidemic spreading.",

keywords = "centrality measures, community detection, epidemic spreading, influence spreading, information spreading, modelling social networks, pseudo-algorithm, scalable algorithm, social media networks, social networks",

author = "Vesa Kuikka and Henrik Aalto and Matias Ij{\"a}s and Kaski, {Kimmo K.}",

note = "Funding Information: We acknowledge that the original idea and software implementation of Algorithm 3 has been a result of the cooperation between Matias Ij{\"a}s and Janne Levijoki [15]. The work of Ij{\"a}s and Levijoki is an efficient implementation of the influence spreading model that was first published in [28]. Publisher Copyright: {\textcopyright} 2022 by the authors.",

year = "2022",

month = aug,

doi = "10.3390/a15080262",

language = "English",

volume = "15",

pages = "1--15",

journal = "Algorithms",

issn = "1999-4893",

publisher = "MDPI AG",

number = "8",

}

TY - JOUR

T1 - Efficiency of Algorithms for Computing Influence and Information Spreading on Social Networks

AU - Kuikka, Vesa

AU - Aalto, Henrik

AU - Ijäs, Matias

AU - Kaski, Kimmo K.

N1 - Funding Information: We acknowledge that the original idea and software implementation of Algorithm 3 has been a result of the cooperation between Matias Ijäs and Janne Levijoki [15]. The work of Ijäs and Levijoki is an efficient implementation of the influence spreading model that was first published in [28]. Publisher Copyright: © 2022 by the authors.

PY - 2022/8

Y1 - 2022/8

N2 - Modelling interactions on complex networks needs efficient algorithms for describing processes on a detailed level in the network structure. This kind of modelling enables more realistic applications of spreading processes, network metrics, and analyses of communities. However, different real-world processes may impose requirements for implementations and their efficiency. We discuss different transmission and spreading processes and their interrelations. Two pseudo-algorithms are presented, one for the complex contagion spreading mechanism using non-self-avoiding paths in the modelling, and one for simple contagion processes using self-avoiding paths in the modelling. The first algorithm is an efficient implementation that can be used for describing social interaction in a social network structure. The second algorithm is a less efficient implementation for describing specific forms of information transmission and epidemic spreading.

AB - Modelling interactions on complex networks needs efficient algorithms for describing processes on a detailed level in the network structure. This kind of modelling enables more realistic applications of spreading processes, network metrics, and analyses of communities. However, different real-world processes may impose requirements for implementations and their efficiency. We discuss different transmission and spreading processes and their interrelations. Two pseudo-algorithms are presented, one for the complex contagion spreading mechanism using non-self-avoiding paths in the modelling, and one for simple contagion processes using self-avoiding paths in the modelling. The first algorithm is an efficient implementation that can be used for describing social interaction in a social network structure. The second algorithm is a less efficient implementation for describing specific forms of information transmission and epidemic spreading.

KW - centrality measures

KW - community detection

KW - epidemic spreading

KW - influence spreading

KW - information spreading

KW - modelling social networks

KW - pseudo-algorithm

KW - scalable algorithm

KW - social media networks

KW - social networks

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

U2 - 10.3390/a15080262

DO - 10.3390/a15080262

M3 - Article

AN - SCOPUS:85137267482

SN - 1999-4893

VL - 15

SP - 1

EP - 15

JO - Algorithms

JF - Algorithms

IS - 8

M1 - 262

ER -

Efficiency of Algorithms for Computing Influence and Information Spreading on Social Networks

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this