TY - GEN
T1 - Finding critical blocks of information diffusion in social networks
AU - Zhang, Ende
AU - Wang, Guoren
AU - Gao, Kening
AU - Yu, Ge
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84879995970&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-38562-9_53
DO - 10.1007/978-3-642-38562-9_53
M3 - Conference contribution
AN - SCOPUS:84879995970
SN - 9783642385612
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 521
EP - 532
BT - Web-Age Information Management - 14th International Conference, WAIM 2013, Proceedings
PB - Springer Verlag
T2 - 14th International Conference on Web-Age Information Management, WAIM 2013
Y2 - 14 June 2013 through 16 June 2013
ER -