Identity and Search in Social Networks

Abstract

Social networks have the surprising property of being "searchable": Ordinary people are capable of directing messages through their network of acquaintances to reach a specific but distant target person in only a few steps. We present a model that offers an explanation of social network searchability in terms of recognizable personal identities: sets of characteristics measured along a number of social dimensions. Our model defines a class of searchable networks and a method for searching them that may be applicable to many network search problems, including the location of data files in peer-to-peer networks, pages on the World Wide Web, and information in distributed databases.

4 page, 3 figures, revtex

References in corpus (4)

• Emergence of scaling in random networks
• Scaling and percolation in the small-world network model
• Search in Power-Law Networks
• Path finding strategies in scale-free networks

Cited by in corpus (145)

• The structure and function of complex networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Mixing patterns in networks
• Critical phenomena in complex networks
• Hierarchical structure and the prediction of missing links in networks
• Hierarchical Organization in Complex Networks
• Quantifying social group evolution
• Networks beyond pairwise interactions: structure and dynamics
• Hyperbolic Geometry of Complex Networks
• Popularity versus Similarity in Growing Networks
• Optimal network topologies for local search with congestion
• Navigability of Complex Networks
• Properties of highly clustered networks
• Cooperation and Contagion in Web-Based, Networked Public Goods Experiments
• Uncovering space-independent communities in spatial networks
• Self-similarity of complex networks and hidden metric spaces
• Graph Evolution: Densification and Shrinking Diameters
• Model of Genetic Variation in Human Social Networks
• Time Critical Social Mobilization: The DARPA Network Challenge Winning Strategy
• Spatial Growth of Real-world Networks
• Random walks and search in time-varying networks
• Formalising the multidimensional nature of social networks
• Greedy Forwarding in Dynamic Scale-Free Networks Embedded in Hyperbolic Metric Spaces
• Efficient local strategies for vaccination and network attack
• A system of mobile agents to model social networks
• Uncovering collective listening habits and music genres in bipartite networks
• Superlinear Scaling for Innovation in Cities
• Curvature and temperature of complex networks
• The Topology of Music Recommendation Networks
• Networks of strong ties
• Directed network modules
• The Structure of Phonological Networks Across Multiple Languages
• Fastest learning in small world neural networks
• Hypergraph reconstruction from network data
• Emergence of Soft Communities from Geometric Preferential Attachment
• Navigable Networks as Nash Equilibria of Navigation Games
• Cover time for random walks on arbitrary complex networks
• Self-avoiding walks on scale-free networks
• Scale Free Networks from Self-Organisation
• Extended navigability of small world networks: exact results and new insights
• Understanding the group dynamics and success of teams
• Preferential attachment of communities: the same principle, but a higher level
• "Birds of a Feather": Does User Homophily Impact Information Diffusion in Social Media?
• Fundamental statistical features and self-similar properties of tagged networks
• Network dynamics of ongoing social relationships
• Asymptotic behavior of the Kleinberg model
• Transmission of severe acute respiratory syndrome in dynamical small-world networks
• Search in weighted complex networks
• A Tractable Complex Network Model based on the Stochastic Mean-field Model of Distance
• Equilibrium statistical mechanics of network structures
• Information Dynamics in the Networked World
• Extremal Properties of Random Structures
• Critical fluctuations in spatial complex networks
• Complex Networks
• Large-scale structural organization of social networks
• Order-disorder phase transition in a cliquey social network
• The Phase Stability Network of all Inorganic Materials
• On the genre-fication of Music: a percolation approach (long version)
• VIP-club phenomenon: emergence of elites and masterminds in social networks
• Sampling from Social Networks with Attributes
• Degree Distribution in Quantum Walks on Complex Networks
• Topological structures in the equities market network
• Detection of node group membership in networks with group overlap
• New approaches to model and study social networks
• Network-Induced Oscillatory Behavior in Material Flow Networks
• Growing network model for community with group structure
• The critical point of k-clique percolation in the Erdos-Renyi graph
• Networks based on collisions among mobile agents
• How Do Networks Become Navigable?
• A general centrality framework based on node navigability
• Homophily as a Process Generating Social Networks: Insights from Social Distance Attachment Model
• Homophily and the Speed of Social Mobilization: The Effect of Acquired and Ascribed Traits
• Navigation in a small world with local information
• Spectral transitions in networks
• Self-Assembly of Information in Networks
• Modeling self-organization of communication and topology in social networks
• The evolution of navigable small-world networks
• Epidemic Variability in Hierarchical Geographical Networks with Human Activity Patterns
• Structure of n-clique networks embedded in a complex network
• Generalization of the small-world effect on a model approaching the Erdős-Rényi random graph
• A Game Theoretical Approach to Modeling Information Dissemination in Social Networks
• Growing community networks with local events
• Targeted Social Mobilisation in a Global Manhunt
• A Game Theoretical Approach to Broadcast Information Diffusion in Social Networks
• Critical stretching of mean-field regimes in spatial networks
• The effect of social interactions in the primary life cycle of motion pictures
• Neighbor selection and hitting probability in small-world graphs
• Features and heterogeneities in growing network models
• Using link and content over time for embedding generation in Dynamic Attributed Networks
• Learning in Hierarchical Social Networks
• Kinetic growth walks on complex networks
• The q-component static model : modeling social networks
• Routes Obey Hierarchy in Complex Networks
• Overlapping modularity at the critical point of k-clique percolation
• Triadic percolation induces dynamical topological patterns in higher-order networks
• Two-dimensional small-world networks: navigation with local information
• Kinetic-growth self-avoiding walks on small-world networks
• The Mesh of Civilizations and International Email Flows
• A Biologically Inspired Model of Distributed Online Communication Supporting Efficient Search and Diffusion of Innovation
• How to search a social network
• Properties of Healthcare Teaming Networks as a Function of Network Construction Algorithms
• Self-organized Emergence of Navigability on Small-World Networks
• Complex systems: features, similarity and connectivity
• Modular hierarchical and power-law small-world networks bear structural optima for minimal first passage times and cover time
• Ecology of active and passive players and their impact on information selection
• Diophantine Networks
• Why are probabilistic laws governing quantum mechanics and neurobiology?
• Greedy Routing and the Algorithmic Small-World Phenomenom
• Toward Understanding Friendship in Online Social Networks
• A novel approach to study realistic navigations on networks
• Greedy Connectivity of Geographically Embedded Graphs
• Predictive Analysis for Social Processes II: Predictability and Warning Analysis
• Tipping the balances of a small world
• Dependence of the average to-node distance on the node degree for random graphs and growing networks
• Incorporating uncertainty into the study of animal social networks
• Measuring and Predicting Speed of Social Mobilization
• Detecting Structure of Complex Network by Quantum Bosonic Dynamics
• Flow descriptors of human mobility networks
• Information Relaxation is Ultradiffusive
• Evolving Graph Representation and Visualization
• Improving Reachability and Navigability in Recommender Systems
• Funnelling effect in networks
• Degree and connectivity of the Internet's scale-free topology
• A quest to unravel the metric structure behind perturbed networks
• Study Of The Fundamental Physical Principles in Atmospheric Modeling Based On Identification Of Atmosphere - Climate Control Factors: Bromine Explosion At The Polar Arctic Sunrise
• Remarks on Category-Based Routing in Social Networks
• Impact of local information in growing networks
• Realistic searches on stretched exponential networks
• Modeling Transitivity in Complex Networks
• The Scaling laws of Spatial Structure in Social Networks
• Double Clustering and Graph Navigability
• The hidden architecture of connections: How do multidimensional identities shape our social networks?
• Automatic hermiticity for mixed states
• Geometric protean graphs
• Coevolution of Cooperation and Partner Rewiring Range in Spatial Social Networks
• The anatomy of urban social networks and its implications in the searchability problem
• Network of social groups or Let's have a party
• Effects of missing data in social networks
• Category-Based Routing in Social Networks: Membership Dimension and the Small-World Phenomenon (Short)
• The Political Significance of Social Penumbras
• Continuous-time quantum walks on ultrametric spaces
• Navigation in non-uniform density social networks
• A Threshold For Clusters in Real-World Random Networks
• Hidden space reconstruction inspires link prediction in complex networks
• A Game Theoretical Approach to Modeling Full-Duplex Information Dissemination