Low-Distortion Inference of Latent Similarities from a Multiplex Social Network

DOI10.1137/130949191zbMath1422.91604arXiv1202.0922OpenAlexW2503048885MaRDI QIDQ5255011

Shiri Chechik, David Kempe, Aleksandrs Slivkins, Ittai Abraham

Publication date: 11 June 2015

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1202.0922

zbMATH Keywords

metric spacesocial network analysissmall world networkssocial distancemultiplex social networks

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Social networks; opinion dynamics (91D30) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (1)

Influence analysis: A survey of the state-of-the-art

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph clustering
• Recovering the long-range links in augmented graphs
• Universal augmentation schemes for network navigability
• Algorithms for next generation networks
• Distance estimation and object location via rings of neighbors
• Could any graph be turned into a small-world?
• Close to optimal decentralized routing in long-range contact networks
• On the searchability of small-world networks with arbitrary underlying structure
• Universal Rigidity and Edge Sparsification for Sensor Network Localization
• The small-world phenomenon
• Triangulation and embedding using small sets of beacons
• Small Worlds as Navigable Augmented Networks: Model, Analysis, and Validation
• Finding nearest neighbors in growth-restricted metrics
• Know thy neighbor's neighbor
• Bypassing the embedding
• A semidefinite programming approach to tensegrity theory and realizability of graphs
• Latent Space Approaches to Social Network Analysis
• The effect of power-law degrees on the navigability of small worlds
• Collective dynamics of ‘small-world’ networks
• Depth of Field and Cautious-Greedy Routing in Social Networks
• Towards fast decentralized construction of locality-aware overlay networks
• Optimal path search in small worlds
• Spatial gossip and resource location protocols
• A Doubling Dimension Threshold Θ(loglogn) for Augmented Graph Navigability
• Navigating Low-Dimensional and Hierarchical Population Networks
• Eclecticism shrinks even small worlds
• Concentration of Measure for the Analysis of Randomized Algorithms

This page was built for publication: Low-Distortion Inference of Latent Similarities from a Multiplex Social Network