The Multi-source Localizaiton Research Of Network Propagation Based On Community Structure

Locating the sources of information diffusion effectively in complex networks in which multiple spreaders exist is significant for forecasting the range of propagation, controlling the process of propagation, etc. Generally, information propagation in a social network is sponsored by several information sources, such as rumors which originate from more than one person. There is some uncertainty in the propagation paths for the sources of information propagation in a social network in virtue of a variety of factors, and influence ranges of multiple sources are mixed with each other in the network, which makes it very difficult to locate the sources. This paper presents a multi-source localization algorithm based on the community structure of network in view of the local property of mufti-source information propagation.Considering the social networks with obvious community structure, we firstly analyze the process of multi-source propagation in a variety of network propagation models including random model, linear threshold model and independent cascade model, and find that the propagation is localized when multiple sources are spreading in a network. Then we analyze the changes over community structure of network for the regular pattern of local propagation, and results show that the value of modularity in the network should be greater than 0.5 in order to ensure the local propagation characteristics under a variety of propagation models.In view of the analysis results for multi-source propagation, we design the multi-source localization algorithm based on the community structure of network. We divide the network into communities with community discovery algorithms of complex network, and find the community structure with which we can separate the mutual influence between sources. Then we can locate the spreader within the community independently with the local observers deployed sparsely in each divided communities. Finally, the algorithm is tested on the real and model networks. Results show that our multi-source localization algorithm is effective in the network with a certain community structure. The proposed localization method is of great significance for locating rumors, controlling infectious diseases, etc.