10/30/22, 5:20 PM L10: How do Dense Clusters Affect Cascades? : Network Science – CS-7280-O01
L10: How do Dense Clusters Affect Cascades?
Image source: Textbook ¡°Networks, Crowds and Markets¡± (https://www.cs.cornell.edu/home/kleinber/net works-book/networks-book-ch19.pdf) book, by Easley and Kleinberg, Chapter 19
We will first prove the following result:
Copyright By PowCoder代写 加微信 powcoder
Suppose that we model the diffusion process using the Linear Threshold Model with threshold value .
If the set of initially active nodes is A, then the cascade will NOT cover the whole network if the network includes a cluster of initially inactive nodes with density greater than .
Proof: We will prove this by contradiction – we start with an assumption, then following a series of steps which leads to a result that cannot be true. Consider such a cluster of initially inactive nodes with density greater than . Assume the opposite of what we want to prove, i.e., that one or more nodes in this cluster eventually become active. Let v be the first such node in the cluster.
At the time v became active, its only active neighbors could be outside the cluster. But since the cluster has density greater than , at least a fraction of v’s neighbors are in the cluster. So, less than a fraction of v’s neighbors are outside the cluster. Even if all of those neighbors were active, that would not be enough to activate v. This leads to a contradiction, and so it cannot be that the cluster eventually includes an active node.
https://gatech. instructure. com/courses/265324/pages/l10-how -do-dense-clusters-aff ect-cascades?module_item_id=2520848 1/2
10/30/22, 5:20 PM L10: How do Dense Clusters Affect Cascades? : Network Science – CS-7280-O01
Moreover, we can show the following related result:
If a network cascade that starts from a set of initial nodes A does not cover the whole network, then the network must include a cluster of density greater than
Food For Thought
Prove the last result stated above. The visualization at the right will help you to think about the proof.
https://gatech. instructure. com/courses/265324/pages/l10-how -do-dense-clusters-aff ect-cascades?module_item_id=2520848 2/2
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com