TY - JOUR
T1 - Who Spread That Rumor
T2 - Finding the Source of Information in Large Online Social Networks with Probabilistically Varying Internode Relationship Strengths
AU - Louni, Alireza
AU - Subbalakshmi, K. P.
N1 - Publisher Copyright:
© 2014 IEEE.
PY - 2018/6
Y1 - 2018/6
N2 - We address the problem of estimating the source of a rumor in large-scale social networks. Previous works studying this problem have mainly focused on graph models with deterministic and homogenous internode relationship strengths. However, internode relationship strengths in real social networks are random. We model this uncertainty by using random, nonhomogenous edge weights on the underlying social network graph. We propose a novel two-stage algorithm that uses the modularity of the social network to locate the source of the rumor with fewer sensor nodes than other existing algorithms. We also propose a novel method to select these sensor nodes. We evaluate our algorithm using a large data set from Twitter and Sina Weibo. Real-world time series data are used to model the uncertainty in social relationship strengths. Simulations show that the proposed algorithm can determine the actual source within two hops, 69%-80% of the time, when the diameter of the networks varies between 7 and 13. Our numerical results also show that it is easier to estimate the source of a rumor when the source has higher betweenness centrality. Finally, we demonstrate that our two-stage algorithm outperforms the alternative algorithm in terms of the accuracy of localizing the source.
AB - We address the problem of estimating the source of a rumor in large-scale social networks. Previous works studying this problem have mainly focused on graph models with deterministic and homogenous internode relationship strengths. However, internode relationship strengths in real social networks are random. We model this uncertainty by using random, nonhomogenous edge weights on the underlying social network graph. We propose a novel two-stage algorithm that uses the modularity of the social network to locate the source of the rumor with fewer sensor nodes than other existing algorithms. We also propose a novel method to select these sensor nodes. We evaluate our algorithm using a large data set from Twitter and Sina Weibo. Real-world time series data are used to model the uncertainty in social relationship strengths. Simulations show that the proposed algorithm can determine the actual source within two hops, 69%-80% of the time, when the diameter of the networks varies between 7 and 13. Our numerical results also show that it is easier to estimate the source of a rumor when the source has higher betweenness centrality. Finally, we demonstrate that our two-stage algorithm outperforms the alternative algorithm in terms of the accuracy of localizing the source.
KW - Partial observation
KW - probabilistic social relationship strength
KW - rumor source estimation
KW - rumor spreading
KW - social networks
UR - http://www.scopus.com/inward/record.url?scp=85042357770&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85042357770&partnerID=8YFLogxK
U2 - 10.1109/TCSS.2018.2801310
DO - 10.1109/TCSS.2018.2801310
M3 - Article
AN - SCOPUS:85042357770
VL - 5
SP - 335
EP - 343
JO - IEEE Transactions on Computational Social Systems
JF - IEEE Transactions on Computational Social Systems
IS - 2
ER -