Finding critical blocks of information diffusion in social networks

Ende Zhang, Guoren Wang, Kening Gao, Ge Yu

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Citation (Scopus)

Abstract

The diffusion of information is taking place every place and every time over the Internet. The widely used web applications of online social networks, have many benefits to serve as a medium for fast, widespread information diffusion platforms. While there is a substantial works on how to maximize the diffusion of useful information, there are many misinformation diffusing on social networks. How to control the misinformation diffusing efficiently with the smallest cost is still a big challenge. We tackle this challenge by reducing the problem to finding the critical blocks. The critical blocks are the sets of nodes that partition the whole network evenly at a small cost, and we believe they play a key role during the process of diffusion. We prove such problem of finding critical blocks is NP-complete and therefore an exact solution is infeasible to get. A simple but effective solution is proposed by the following steps: first we convert a social network graph into a Laplacian matrix, then we compute its Fiedler Vector, which has been proved to have good properties, with the help of Fiedler Vector, we develop some heuristic algorithms to find critical blocks. We also perform lots of experiments both on synthetic data and real world datasets of Twitter, the experimental results show that our algorithm is effective and efficient both on synthetic data and real world data.

Original languageEnglish
Title of host publicationWeb-Age Information Management - 14th International Conference, WAIM 2013, Proceedings
PublisherSpringer Verlag
Pages521-532
Number of pages12
ISBN (Print)9783642385612
DOIs
Publication statusPublished - 2013
Externally publishedYes
Event14th International Conference on Web-Age Information Management, WAIM 2013 - Beidaihe, China
Duration: 14 Jun 201316 Jun 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7923 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th International Conference on Web-Age Information Management, WAIM 2013
Country/TerritoryChina
CityBeidaihe
Period14/06/1316/06/13

Fingerprint

Dive into the research topics of 'Finding critical blocks of information diffusion in social networks'. Together they form a unique fingerprint.

Cite this