Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Nhận diện hiệu quả các điểm khởi phát của dịch bệnh trong một đồ thị lớn
Tóm tắt
Dựa trên một bức ảnh tĩnh của một đồ thị lớn, trong đó một căn bệnh đã lây lan trong một khoảng thời gian, liệu chúng ta có thể xác định được những nút nào là điểm khởi phát khiến bệnh lây lan? Nói cách khác, liệu chúng ta có thể xác định đáng tin cậy ai là tác nhân gây bệnh? Trong bài báo này, chúng tôi trả lời câu hỏi này một cách khẳng định và đưa ra một phương pháp hiệu quả có tên là NetSleuth cho mô hình lây lan virus nhiễm bệnh được biết đến là nhạy cảm-nhiễm. Cốt lõi của nghiên cứu là xác định tập hợp các nút nguyên mẫu giải thích tốt nhất cho bức ảnh tĩnh đã cho. Chúng tôi đề xuất sử dụng nguyên tắc độ dài mô tả tối thiểu để xác định tập hợp nút nguyên mẫu và sóng lây lan virus tốt nhất, trong đó mà chúng tôi có thể mô tả đồ thị bị nhiễm một cách súc tích nhất. Chúng tôi cung cấp một thuật toán cực kỳ hiệu quả để xác định các tập hợp nút nguyên mẫu có thể xảy ra dựa trên bức ảnh tĩnh. Sau đó, với các nút nguyên mẫu này, chúng tôi cho thấy có thể tối ưu hóa sóng lây lan virus một cách có hệ thống bằng cách tối đa hóa xác suất. Khi kết hợp cả ba yếu tố này, NetSleuth có thể tự động xác định số lượng nút nguyên mẫu chính xác, cũng như xác định những nút nào là tác nhân gây bệnh. Các thí nghiệm về phương pháp của chúng tôi cho thấy độ chính xác cao trong việc phát hiện các nút nguyên mẫu, bên cạnh việc tự động xác định chính xác số lượng của chúng. Hơn nữa, NetSleuth cho phép mở rộng tuyến tính theo số lượng nút của đồ thị.
Từ khóa
#mô hình lây lan bệnh #đồ thị lớn #điểm khởi phát #NetSleuth #thuật toán hiệu quả #phát hiện nút nguyên mẫuTài liệu tham khảo
Anderson RM, May RM (1991) Infectious diseases of humans: dynamics and control. Oxford University Press, Oxford
Bikhchandani S, Hirshleifer D, Welch I (1992) A theory of fads, fashion, custom, and cultural change in informational cascades. Polit Econ 100(5):992–1026
Briesemeister L, Lincoln P, Porras P (2003) Epidemic profiles and defense of scale-free networks. In: WORM 2003, Washington, DC
Cilibrasi R, Vitányi P (2005) Clustering by compression. IEEE Trans Inf Technol 51(4):1523–1545
Cover TM, Thomas JA (2006) Elements of information theory. Wiley-Interscience, New York, pp 110–112
Cvetković DM, Doob M, Sachs H (1998) Spectra of graphs: theory and applications, 3rd edn
Chakrabarti D, Papadimitriou S, Modha DS, Faloutsos C (2004) Fully automatic cross-associations. In: Proceedings of the 10th ACM international conference on knowledge discovery and data mining (SIGKDD), Seattle, WA, pp 79–88
Chakrabarti D, Wang Y, Wang C, Leskovec J, Faloutsos C (2008) Epidemic thresholds in real networks. TISSEC 10(4)
Chen W, Wang C, Wang Y (2010) Scalable influence maximization for prevalent viral marketing in large-scale social networks. In: Proceedings of the 16th ACM SIGKDD international conference on knowledge discovery and data mining (KDD ’10). ACM, New York, pp 1029–1038. doi:10.1145/1835804.1835934. http://doi.acm.org/10.1145/1835804.1835934
Faloutsos C, Megalooikonomou V (2007) On data mining, compression and Kolmogorov complexity. In: Webb G (ed) Data mining and knowledge discovery, vol 15. Springer, Berlin, pp 3–20
Grünwald P (2007) The minimum description length principle. MIT Press, Cambridge
Goldenberg J, Libai B, Muller E (2001) Talk of the network: a complex systems look at the underlying process of word-of-mouth. Market Lett 12(3):211–223
Gruhl D, Guha R, Liben-Nowell D, Tomkins A (2004) Information diffusion through blogspace. In: Proceedings of the 13th international conference on World Wide Web (WWW)
Ganesh A, Massoulié L, Towsley D (2005) The effect of network topology on the spread of epidemics. In: INFOCOM
Goyal A, Lu W, Lakshmanan LVS (2011) Simpath: an efficient algorithm for influence maximization under the linear threshold model. In: Proceedings of the 11th IEEE international conference on data mining (ICDM), Vancouver, Canada
Kephart JO, White SR (1993) Measuring and modeling computer virus prevalence. In: SP
Kempe D, Kleinberg J, Tardos E (2003) Maximizing the spread of influence through a social network. In: Proceedings of the 9th ACM international conference on knowledge discovery and data mining (SIGKDD), Washington, DC
Li M, Vitányi P (1993) An introduction to Kolmogorov complexity and its applications. Springer, Berlin
Leskovec J, Adamic LA, Huberman BA (2006) The dynamics of viral marketing. In: EC
Leskovec J, Krause A, Guestrin C, Faloutsos C, VanBriesen J, Glance NS (2007a) Cost-effective outbreak detection in networks. In: Proceedings of the 13th ACM international conference on knowledge discovery and data mining (SIGKDD), San Jose, CA, pp 420–429
Leskovec J, McGlohon M, Faloutsos C, Glance N, Hurst M (2007b) Cascading behavior in large blog graphs: patterns and a model. In: Proceedings of the 7th SIAM international conference on data mining (SDM), Minneapolis, MN
Lappas T, Terzi E, Gunopulos D, Mannila H (2010) Finding effectors in social networks. In: Proceedings of the 16th ACM international conference on knowledge discovery and data mining (SIGKDD), Washington, DC, pp 1059–1068
McCuler CR (2000) The many proofs and applications of Perron’s theorem. SIAM Rev 42:1
Pastor-Santorras R, Vespignani A (2001) Epidemic spreading in scale-free networks. Phys Rev Lett 86:14
Prakash BA, Tong H, Valler N, Faloutsos M, Faloutsos C (2010) Virus propagation on time-varying networks: theory and immunization algorithms. In: Proceedings of the European conference on machine learning and principles and practice of knowledge discovery in databases (ECML PKDD), Barcelona, Spain
Prakash BA, Chakrabarti D, Faloutsos M, Valler N, Faloutsos C (2011) Threshold conditions for arbitrary cascade models on arbitrary networks. In: Proceedings of the 11th IEEE international conference on data mining (ICDM), Vancouver, Canada
Prakash BA, Chakrabarti D, Valler N, Faloutsos M, Faloutsos C (2012) Threshold conditions for arbitrary cascade models on arbitrary networks. Knowl Inf Syst 33(3):549–575
Rissanen J (1978) Modeling by shortest data description. Automatica 14(1):465–471
Rissanen J (1983) Modeling by shortest data description. Ann Stat 11(2):416–431
Richardson M, Domingos P (2002) Mining knowledge-sharing sites for viral marketing. In: Proceedings of the 8th ACM international conference on knowledge discovery and data mining (SIGKDD), Edmonton, Alberta
Roos T, Rissanen J (2008) On sequentially normalized maximum likelihood models. In: Proceedings of the workshop on information theoretic methods in science and engineering (WITMSE)
Saito K, Kimura M, Ohara K, Motoda H (2012) Efficient discovery of influential nodes for sis models in social networks. Knowl Inf Syst 30(3):613–635
Schwarz G (1978) Estimating the dimension of a model. Ann Stat 6(2):461–464
Strang G (1988) Linear algebra and its applications, 3rd edn. Harcourt Brace Jonanovich, San Diego
Shah D, Zaman T (2010) Detecting sources of computer viruses in networks: theory and experiment. In: SIGMETRICS, pp 203–214
Shah D, Zaman T (2011) Rumors in a network: who’s the culprit? IEEE Trans Inf Technol 57(8):5163–5181
Smets K, Vreeken J (2011) The odd one out: Identifying and characterising anomalies. In: Proceedings of the 11th SIAM international conference on data mining (SDM), Mesa, AZ, society for industrial and applied mathematics (SIAM), pp 804–815
Tong H, Prakash BA, Tsourakakis CE, Eliassi-Rad T, Faloutsos C, Chau DH (2010) On the vulnerability of large graphs. In: Proceedings of the 10th IEEE international conference on data mining (ICDM), Sydney, Australia
Vereshchagin N, Vitanyi P (2004) Kolmogorov’s structure functions and model selection. IEEE Trans Inf Technol 50(12):3265–3290
Vreeken J, van Leeuwen M, Siebes A (2011) Krimp: mining itemsets that compress. Data Min Knowl Discov 23(1):169–214
Wallace C (2005) Statistical and inductive inference by minimum message length. Springer, Berlin
Zhao J, Wu J, Feng X, Xiong H, Xu K (2011) Information propagation in online social networks: a tie-strength perspective. Knowl Inf Syst. 1–20. doi:10.1007/s10115-011-0445-x