Identifying Propagation Sources in Networks: State-of-the-Art and Comparative Studies
Top Cited Papers
- 4 October 2016
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Communications Surveys & Tutorials
- Vol. 19 (1) , 465-481
Abstract
It has long been a significant but difficult problem to identify propagation sources based on limited knowledge of network structures and the varying states of network nodes. In practice, real cases can be locating the sources of rumors in online social networks and finding origins of a rolling blackout in smart grids. This paper reviews the state-of-the-art in source identification techniques and discusses the pros and cons of current methods in this field. Furthermore, in order to gain a quantitative understanding of current methods, we provide a series of experiments and comparisons based on various environment settings. Especially, our observation reveals considerable differences in performance by employing different network topologies, various propagation schemes, and diverse propagation probabilities. We therefore reach the following points for future work. First, current methods remain far from practice as their accuracy in terms of error distance (δ) is normally larger than three in most scenarios. Second, the majority of current methods are too time consuming to quickly locate the origins of propagation. In addition, we list five open issues of current methods exposed by the analysis, from the perspectives of topology, number of sources, number of networks, temporal dynamics, and complexity and scalability. Solutions to these open issues are of great academic and practical significance.Keywords
This publication has 65 references indexed in Scilit:
- Network forensicsACM SIGMETRICS Performance Evaluation Review, 2012
- Rumor centralityACM SIGMETRICS Performance Evaluation Review, 2012
- Controllability of complex networksNature, 2011
- Characterizing the Dynamical Importance of Network Nodes and LinksPhysical Review Letters, 2006
- Attack vulnerability of complex networksPhysical Review E, 2002
- Practical network support for IP tracebackACM SIGCOMM Computer Communication Review, 2000
- Error and attack tolerance of complex networksNature, 2000
- Eccentricity and centrality in networksSocial Networks, 1995
- Power and Centrality: A Family of MeasuresAmerican Journal of Sociology, 1987
- Centrality in social networks conceptual clarificationSocial Networks, 1978