Finding critical blocks of information diffusion in social networks

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 are 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, and the nodes in critical blocks have advantages to span different communities in some social networks too. 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 perform lots of experiments both on synthetic data, real world datasets from Twitter and coauthor networks from DBLP, the experimental results show that our algorithm is effective and efficient both on synthetic data and real world data. And we demonstrate a case analysis as an anecdotal evidence to show there do exist critical blocks in social networks and our algorithm can find them effectively and efficiently.