An Analysis of How User Random Walks Influence Information Diffusion in Social Networking Websites

Qian XIAO; Haitao XIE

doi:10.1587/transfun.E98.A.2129

An Analysis of How User Random Walks Influence Information Diffusion in Social Networking Websites

Qian XIAO, Haitao XIE

Full Text Views

0

Share
Cite this

Summary :

In social websites, users acquire information from adjacent neighbors as well as distant users by seeking along hyperlinks, and therefore, information diffusions, also seen as processes of “user infection”, show both cascading and jumping routes in social networks. Currently, existing analysis suffers from the difficulty in distinguishing between the impacts of information seeking behaviors, i.e. random walks, and other factors leading to user infections. To this end, we present a mechanism to recognize and measure influences of random walks on information diffusions. Firstly, we propose the concept of information propagation structure (IPS), which is also a directed acyclic graph, to represent frequent information diffusion routes in social networks. In IPS, we represent “jumping routes” as virtual arcs and regard them as the traces of random walks. Secondly, we design a frequent IPS mining algorithm (FIPS). By considering descendant node infections as a consequence of ancestor node infections in IPS, we can use a Bayesian network to model each IPS, and learn parameters based on the records of information diffusions passing through the IPS. Finally, we present a quantitative description method of random walks influence, the method is based on Bayesian probabilistic inferring in IPS, which is used to determine the ancestors, whose infection causes the infection of target users. We also employ betweenness centralities of arcs to evaluate contributions of random walks to certain infections. Experiments are carried out with real datasets and simulations. The results show random walks are influential in early and steady phases of information diffusions. They help diffusions pass through some topology limitations in social networks.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E98-A No.10 pp.2129-2138

Publication Date: 2015/10/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E98.A.2129

Type of Manuscript: PAPER

Category: Graphs and Networks

Authors

Qian XIAO
Beijing Institute of Graphic Communication
Haitao XIE
Beijing University of Chemical Technology

Keyword

information diffusion, random walk, social network, Bayesian network

Cite this

Copy

Qian XIAO, Haitao XIE, "An Analysis of How User Random Walks Influence Information Diffusion in Social Networking Websites" in IEICE TRANSACTIONS on Fundamentals, vol. E98-A, no. 10, pp. 2129-2138, October 2015, doi: 10.1587/transfun.E98.A.2129.
Abstract: In social websites, users acquire information from adjacent neighbors as well as distant users by seeking along hyperlinks, and therefore, information diffusions, also seen as processes of “user infection”, show both cascading and jumping routes in social networks. Currently, existing analysis suffers from the difficulty in distinguishing between the impacts of information seeking behaviors, i.e. random walks, and other factors leading to user infections. To this end, we present a mechanism to recognize and measure influences of random walks on information diffusions. Firstly, we propose the concept of information propagation structure (IPS), which is also a directed acyclic graph, to represent frequent information diffusion routes in social networks. In IPS, we represent “jumping routes” as virtual arcs and regard them as the traces of random walks. Secondly, we design a frequent IPS mining algorithm (FIPS). By considering descendant node infections as a consequence of ancestor node infections in IPS, we can use a Bayesian network to model each IPS, and learn parameters based on the records of information diffusions passing through the IPS. Finally, we present a quantitative description method of random walks influence, the method is based on Bayesian probabilistic inferring in IPS, which is used to determine the ancestors, whose infection causes the infection of target users. We also employ betweenness centralities of arcs to evaluate contributions of random walks to certain infections. Experiments are carried out with real datasets and simulations. The results show random walks are influential in early and steady phases of information diffusions. They help diffusions pass through some topology limitations in social networks.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/transfun.E98.A.2129/_p

Copy

@ARTICLE{e98-a_10_2129,
author={Qian XIAO, Haitao XIE, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An Analysis of How User Random Walks Influence Information Diffusion in Social Networking Websites},
year={2015},
volume={E98-A},
number={10},
pages={2129-2138},
abstract={In social websites, users acquire information from adjacent neighbors as well as distant users by seeking along hyperlinks, and therefore, information diffusions, also seen as processes of “user infection”, show both cascading and jumping routes in social networks. Currently, existing analysis suffers from the difficulty in distinguishing between the impacts of information seeking behaviors, i.e. random walks, and other factors leading to user infections. To this end, we present a mechanism to recognize and measure influences of random walks on information diffusions. Firstly, we propose the concept of information propagation structure (IPS), which is also a directed acyclic graph, to represent frequent information diffusion routes in social networks. In IPS, we represent “jumping routes” as virtual arcs and regard them as the traces of random walks. Secondly, we design a frequent IPS mining algorithm (FIPS). By considering descendant node infections as a consequence of ancestor node infections in IPS, we can use a Bayesian network to model each IPS, and learn parameters based on the records of information diffusions passing through the IPS. Finally, we present a quantitative description method of random walks influence, the method is based on Bayesian probabilistic inferring in IPS, which is used to determine the ancestors, whose infection causes the infection of target users. We also employ betweenness centralities of arcs to evaluate contributions of random walks to certain infections. Experiments are carried out with real datasets and simulations. The results show random walks are influential in early and steady phases of information diffusions. They help diffusions pass through some topology limitations in social networks.},
keywords={},
doi={10.1587/transfun.E98.A.2129},
ISSN={1745-1337},
month={October},}

Copy

TY - JOUR
TI - An Analysis of How User Random Walks Influence Information Diffusion in Social Networking Websites
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2129
EP - 2138
AU - Qian XIAO
AU - Haitao XIE
PY - 2015
DO - 10.1587/transfun.E98.A.2129
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E98-A
IS - 10
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - October 2015
AB - In social websites, users acquire information from adjacent neighbors as well as distant users by seeking along hyperlinks, and therefore, information diffusions, also seen as processes of “user infection”, show both cascading and jumping routes in social networks. Currently, existing analysis suffers from the difficulty in distinguishing between the impacts of information seeking behaviors, i.e. random walks, and other factors leading to user infections. To this end, we present a mechanism to recognize and measure influences of random walks on information diffusions. Firstly, we propose the concept of information propagation structure (IPS), which is also a directed acyclic graph, to represent frequent information diffusion routes in social networks. In IPS, we represent “jumping routes” as virtual arcs and regard them as the traces of random walks. Secondly, we design a frequent IPS mining algorithm (FIPS). By considering descendant node infections as a consequence of ancestor node infections in IPS, we can use a Bayesian network to model each IPS, and learn parameters based on the records of information diffusions passing through the IPS. Finally, we present a quantitative description method of random walks influence, the method is based on Bayesian probabilistic inferring in IPS, which is used to determine the ancestors, whose infection causes the infection of target users. We also employ betweenness centralities of arcs to evaluate contributions of random walks to certain infections. Experiments are carried out with real datasets and simulations. The results show random walks are influential in early and steady phases of information diffusions. They help diffusions pass through some topology limitations in social networks.
ER -