Collective dynamics of ‘small-world’ networks

By Duncan J. Watts, Steven H. Strogatz. 1998

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

Citations in the corpus

Inductive Representation Learning on Large Graphs (2017, neutral): “As a case-study, we consider whether GraphSAGE can learn to predict the clustering coefﬁcient of a node, i.e., the proportion of triangles that are closed within the node’s 1-hop neighborhood [38].”
Big Bird: Transformers for Longer Sequences (2020, background): “A particular model introduced by Watts and Strogatz [95] is of high relevance to us as it achieves a good balance between average shortest path and the notion of locality.”
Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs (2016, background): “…Terms—Graph and tree search strategies, artificial intelligence, information search and retrieval, information storage and retrieval, information technology and systems, search process, graphs and networks, data structures, nearest neighbor search, big data, approximate search, similarity search Ç”
Gossip Dual Averaging for Decentralized Optimization of Pairwise Functions (2016, neutral): “For any i ∈ [ n ] and any t ≥ 0 , let z i ( t ) ∈ R d and ¯ θ i ( t ) ∈ R d be generated according to Algorithm 2.”
Is the Sample Good Enough? Comparing Data from Twitter's Streaming API with Twitter's Firehose (2013, methodology): “To describe the structure of the retweet networks we calculate the clustering coefﬁcient, a measure for local density (Watts and Strogatz 1998).”
Graphite: Iterative Generative Modeling of Graphs (2018, background): “small diameter and hence the generated graphs exhibit strong local clustering (Watts and Strogatz, 1998), the Barabasi-Albert models preferential attachment whereby nodes high-degree nodes are likely to form edges with newly added nodes (Barabasi and Albert, 1999), and Kronecker graph models generat”
Learning Deep Generative Models of Graphs (2018, background): “Another class of graph models aim to capture the small diameter and local clustering properties in graphs, like the small-world model (Watts & Strogatz, 1998).”
Exploring Randomly Wired Neural Networks for Image Recognition (2019, methodology): “To reduce bias from us—the authors of this paper—on the generators, we use three classical families of random graph models in graph theory [52]: the Erdős-Rényi (ER) [7], Barabási-Albert (BA) [1], and Watts-Strogatz (WS) [51] models.”
DAGs with NO TEARS: Continuous Optimization for Structure Learning (2018, background): “Since real-world networks often exhibit scale-free and small-world topologies (Watts and Strogatz, 1998; Barab´asi and Albert, 1999) with highly connected hub nodes, these kinds of structural assumptions are not only diﬃcult to satisfy, but impossible to check.”
Community detection in graphs (2009, methodology): “(Center) Small world graph á la Watts-Strogatz, with 100 vertices and a rewiring probability p = 0.1.”
Graph evolution: Densification and shrinking diameters (2006, background): “(B) Slowly growing diameter assumption: The diameter is a slowly growing function of the network size, as in “small world” graphs [6, 11, 38, 50 ].”
Inductive biases for deep learning of higher-level cognition (2020, background): “Combining these different kinds of inter-module communication modalities in deep network thus seems well advised as well (Watts and Strogatz, 1998; Latora and Marchiori, 2001; Rahaman et al., 2020): (1) Modules which are near each other in the brain layout can probably communicate directly without t”
Permutation Invariant Graph Generation via Score-Based Generative Modeling (2020, background): “, 2019), as well as research in network science (Watts and Strogatz, 1998; Albert and Barabási, 2002; Leskovec et al., 2010).”