Abstract
The cascade capacity of a network is the largest threshold fraction of neighbors that should have made a unanimous decision to result in a complete information cascade. The current approach (based on the intra cluster densities of the bridge nodes of the clusters) used to determine the cascade capacity of a network is independent of the choice of the initial adopters. The authors claim that the above approach gives only a lower bound for the cascade capacity of a network and show that the cascade capacity of a network could be indeed larger if the number and topological positions of the nodes chosen as initial adopters are taken into consideration. In this context, they propose a binary search algorithm that could be used to determine the largest possible cascade capacity of a network for a given set of initial adopters. They run the algorithm on 60 real-world networks of diverse domains and observe the cascade capacity of the networks to increase with the percentage of nodes chosen as initial adopters as well as vary with the choice of the centrality metric used to choose the initial adopters.
TopIntroduction
Information Cascade in network theory is a behavioral phenomenon by which every node arrives at a decision (adopt or reject a particular thing) under the influence of the decision taken by its neighbor nodes (Easley & Kleinberg, 2010). The decision could be with regards to anything like adopting a new technology, supporting a particular political party or leader, choosing a lawn maintenance company, eating in a restaurant, etc. Given an initial set of nodes (called the initial adopters), the phenomena of information cascade (Easley & Kleinberg, 2010) goes through a series of iterations in each of which at least one node (that has not yet taken a decision) takes the decision under the influence of the decision taken by its neighbor nodes. The iterations stop when all the nodes have taken a decision or when no new node (i.e., no node other than those who had decided in the previous iterations) takes a decision in an iteration.
We refer to the information cascade as a complete information cascade (Easley & Kleinberg, 2010) if all the nodes arrive at a unanimous decision (for example: all nodes in a social network decide to support a particular political party in an upcoming election). For complete information cascade to happen, nodes (even if they have their own opinion) are expected to get influenced by the decision of their neighbor nodes so that the decision is eventually unanimous when the iterations stop. We assume a node will be in a position to take the unanimous decision when at least a threshold fraction of its neighbor nodes have taken/adopted the same decision (Easley & Kleinberg, 2010). For a given set of initial adopters, the maximum value for such a threshold fraction of adopted neighbor nodes in every neighborhood that can eventually enforce a unanimous decision for the entire network is called the cascade capacity of the network (Easley & Kleinberg, 2010).
The current approach (Easley & Kleinberg, 2010) used to determine the cascade capacity of a network is to first determine the clusters of the network and then determine their densities. The density of a cluster is the minimum of the intra cluster density (fraction of the incident edges to nodes within the same cluster) of the bridge nodes of the cluster (nodes that have one or more edges to nodes in other clusters). Information cascade can penetrate to a cluster and be complete only if the threshold fraction of adopted neighbor nodes (needed for adopting a unanimous decision) is less than or equal to 1 - the cluster density (Easley & Kleinberg, 2010). The cascade capacity of a network is the minimum of such threshold fractions of adopted neighbor nodes needed for a unanimous decision (Easley & Kleinberg, 2010). A primary weakness with the above approach is that it does not consider the nodes chosen as initial adopters to kick start information cascade while determining the cascade capacity of the network (also reported by Chesney, 2017). We claim that the above approach only gives a lower bound for the cascade capacity of the network and the cascade capacity of the network could be indeed larger if the initial adopters are also considered. Moreover, the above approach is time consuming as it first requires to identify the clusters of a network and then identify the bridge nodes per cluster as well as determine their intra cluster density.
Key Terms in this Chapter
Information Cascade: A behavioral phenomenon by which every node arrives at a decision (adopt or reject a particular thing) under the influence of the decision taken by its neighbor nodes.
Initial Adopters: A set of nodes that trigger information cascade.
Complete Information Cascade: An information cascade in which all the nodes arrive at the same decision irrespective of their personal choice.
Cluster: A grouping of the nodes in a network such that the density of links among nodes within the cluster is larger compared to the density of links to nodes outside the cluster.
Degree: The number of neighbors for a node.
Binary Search: An algorithmic design strategy that proceeds by reducing the search space by half in each iteration until the solution is found or the search space no longer exists.
Cascade Capacity: The largest value for the threshold fraction of neighbors that should have made a unanimous decision to result in a complete information cascade.
Diffusion: Propagation of information from the initial adopters to the rest of the nodes in a network.
Centrality Metric: A scalar value that quantifies the topological importance of a node.
Bridge Node: A node that has links to one or more nodes in other clusters.