Long ties accelerate noisy threshold-based contagions
By: Dean Eckles, Elchanan Mossel, M. Amin Rahimian, Subhabrata Sen
Network structure can affect when and how widely new ideas, products, and
behaviors are adopted. In widely-used models of biological contagion,
interventions that randomly rewire edges (generally making them "longer")
accelerate spread. However, there are other models relevant to social
contagion, such as those motivated by myopic best-response in games with
strategic complements, in which an individual's behavior is described by a
threshol... more
Network structure can affect when and how widely new ideas, products, and
behaviors are adopted. In widely-used models of biological contagion,
interventions that randomly rewire edges (generally making them "longer")
accelerate spread. However, there are other models relevant to social
contagion, such as those motivated by myopic best-response in games with
strategic complements, in which an individual's behavior is described by a
threshold number of adopting neighbors above which adoption occurs (i.e.,
complex contagions). Recent work has argued that highly clustered, rather than
random, networks facilitate spread of these complex contagions. Here we show
that minor modifications to this model, which make it more realistic, reverse
this result, thereby harmonizing qualitative facts about how network structure
affects contagion. To model the trade-off between long and short edges we
analyze the rate of spread over networks that are the union of circular
lattices and random graphs on $n$ nodes. Allowing for noise in adoption
decisions (i.e., adoptions below threshold) to occur with order $1/\sqrt{n}$
probability along some "short" cycle edges) is enough to ensure that random
rewiring accelerates spread. This conclusion continues to hold true under
partial but frequent enough rewiring and when adoption decisions are reversible
but infrequently so. Simulations illustrate the robustness of these results to
several variations on this noisy best-response behavior. Hypothetical
interventions that randomly rewire existing edges or add random edges (versus
adding "short", triad-closing edges) in hundreds of empirical social networks
reduce time to spread. This revised conclusion suggests that those wanting to
increase spread should induce formation of long ties, rather than triad-closing
ties. More generally, this highlights the importance of noise in game-theoretic
analyses of behavior.
less
MetaGraph2Vec: Complex Semantic Path Augmented Heterogeneous Network Embedding
By: Daokun Zhang, Jie Yin, Xingquan Zhu, Chengqi Zhang
Network embedding in heterogeneous information networks (HINs) is a
challenging task, due to complications of different node types and rich
relationships between nodes. As a result, conventional network embedding
techniques cannot work on such HINs. Recently, metapath-based approaches have
been proposed to characterize relationships in HINs, but they are ineffective
in capturing rich contexts and semantics between nodes for embedding learni... more
Network embedding in heterogeneous information networks (HINs) is a
challenging task, due to complications of different node types and rich
relationships between nodes. As a result, conventional network embedding
techniques cannot work on such HINs. Recently, metapath-based approaches have
been proposed to characterize relationships in HINs, but they are ineffective
in capturing rich contexts and semantics between nodes for embedding learning,
mainly because (1) metapath is a rather strict single path node-node
relationship descriptor, which is unable to accommodate variance in
relationships, and (2) only a small portion of paths can match the metapath,
resulting in sparse context information for embedding learning. In this paper,
we advocate a new metagraph concept to capture richer structural contexts and
semantics between distant nodes. A metagraph contains multiple paths between
nodes, each describing one type of relationships, so the augmentation of
multiple metapaths provides an effective way to capture rich contexts and
semantic relations between nodes. This greatly boosts the ability of
metapath-based embedding techniques in handling very sparse HINs. We propose a
new embedding learning algorithm, namely MetaGraph2Vec, which uses metagraph to
guide the generation of random walks and to learn latent embeddings of
multi-typed HIN nodes. Experimental results show that MetaGraph2Vec is able to
outperform the state-of-the-art baselines in various heterogeneous network
mining tasks such as node classification, node clustering, and similarity
search.
less
Seeding with Costly Network Information
By: Dean Eckles, Hossein Esfandiari, Elchanan Mossel, M. Amin Rahimian
The article addresses a fundamental problem in network science: how to target interventions in a social network to maximize the spread of, e.g., adoption of a product. The computational and algorithmic foundations of this problem are well studied when the network structure is known, but it often is not and is expensive or impractical to measure. Here we analyze the case when the network structure is not available but can be acquired through c... more
The article addresses a fundamental problem in network science: how to target interventions in a social network to maximize the spread of, e.g., adoption of a product. The computational and algorithmic foundations of this problem are well studied when the network structure is known, but it often is not and is expensive or impractical to measure. Here we analyze the case when the network structure is not available but can be acquired through costly actions. less