[Small-worlds] [Random graphs and generalizations][LR-percolation] [Networks] [P2P] [Complex Networks] [Metrics] [Hashing] [Others]
Milgram, Stanley.
"The Small World Problem".
Psychology Today, May 1967. pp 60 - 67 D.
J. Kleinberg, The Small-World Phenomenon: An Algorithmic Perspective, STOC’2000.
J. Kleinberg, “Small-World Phenomena and the Dynamics of Information", NIPS'01.
L. Barrière, P. Fraigniaud,
E. Kranakis,
D. Krizanc:
Efficient Routing in Networks with
J. Aspnes, Z. Diamadi and G. Shah, Fault-tolerant routing in peer-to-peer systems, PODC’2002, pp. 223-232. Submitted to Distributed Computing. Available as arXiv:cs.DS/0302022.
G. Manku, M. Naor, and U. Wieder. Know Thy Neighbor's Neighbor: The Power of Lookahead in Randomized P2P Networks. In Proc. of ACM Symp. on Theory of Computing (STOC), 2004
P. Fraigniaud, C. Gavoille, and C. Paul, “Eclecticism Shrinks Even Small Worlds”, In Proc. of 23rd ACM Symp. on Principles of Distributed Computing (PODC 2004).
C. Martel, V. Nguyen: Analyzing Kleinberg's (and other) small-world Models. PODC 2004: 179-188
V. Nguyen, C. Martel: Analyzing and characterizing small-world graphs. SODA 2005: 311-320
M. Flammini, L. Moscardelli, A. Navarra, S. Pérennes: Asymptotically Optimal Solutions for Small World Graphs. DISC 2005: 414-428
E. Lebhar, N. Schabanel: Almost Optimal Decentralized Routing in Long-Range Contact Networks. ICALP 2004: 894-905
A. Slivkins: Distance estimation and object location via rings of neighbors. PODC 2005: 41-50
P. Duchon,
N. Hanusse,
E. Lebhar,
P. Fraigniaud: Greedy Routing in Tree-Decomposed Graphs. ESA 2005: 791-802
G. Sharma, R. Mazumdar , “Hybrid
sensor networks: a small world”, MobiHoc’05
A. Reznik, S.R. Kulkarni, P. Viswanath, A "SMALL WORLD" APPROACH TO HETEROGENEOUS NETWORKS,
A. Helmy, "Small Worlds in Wireless Networks", IEEE Communications Letters, pp. 490-492, Vol. 7, No. 10, October 2003
H. Zhang, A. Goel and R. Gividan, Using the Small-World Model to Improve Freenet Performance, Proc. IEEE Infocom, 2002.
D. Malkhi, M. Naor, D. Ratajczak, Viceroy: A Scalable and Dynamic Emulation of the Butterfly, Proc. 21st ACM Symp. on Princ. of Dist. Comp., p. 183-192.
G. Manku, M. Bawa, P. Raghavan: Symphony: Distributed Hashing in a Small World. USENIX Symposium on Internet Technologies and Systems 2003
D. Kempe, J. Kleinberg, A. Demers, Spatial gossip and resource location protocols, in Proc. 33rd ACM Symposium on Theory of Computing, 2001.
, “Analysis of Wired Short Cuts in Wireless
Sensor Networks”, ICPS'04
pp. 167-176.
V. Nguyen & C. Martel, “Designing Networks for Low Weight, Small Routing Diameter and Low Congestion”. A shorten version to appear in Infocom’06.
S.N. Dorogovtsev and J.F.F. Mendes, ``Exactly solvable small-world network", Europhys. Lett. 50 (1) 1-7 (2000); cond-mat/9907445.
A. Barrat and M. Weight, "On the properties of small-world network models", Eur. Phys. J. B, 13, 547 (2000).
C. Moore and M. E. J. Newman, ``Epidemics and percolation in small-world networks", Phys. Rev. E 61, 5678-5682 (2000).
M. E. J. Newman, ``Models of the small world", J. Stat. Phys. 101, 819-841 (2000).
M. E. Newman, C. Moore and D. J. Watts, ``Mean-field solution of the small-world network model",Phys. Rev. Lett. 84, 3201-3204 (2000).
W. Aiello, F. Chung, L. Lu. Random evolution of massive graphs. Handbook of Massive Data Sets, (Eds. James Abello et al.), Kluwer, 2002, pages 97-122.
B. Bollobas, ``The Diameter of Random Graphs", IEEE Trans. Inform. Theory 36 (1990), no. 2, 285-288.
B. Bollobas, F.R.K. Chung, ``The diameter of a cycle plus a random matching", SIAM J. Discrete Math. 1,328 (1988)
B. Bollobas, “Random Graphs”, Academic Press,
B. Bollobas, ``Random Graphs", Proc. of Symposia in Applied Math. 44,1 (1991).
P. Erdos and A. Renyi, ``On random graphs", Publicationes Mathematicas 6, 290-297 (1959).
F. Chung and L. Lu, ``The Diameter of Random Sparse Graphs", Advances in Applied Math. 26 (2001), 257-279.
M. E. J. Newman, Random graphs as models of networks, in Handbook of
Graphs and Networks, S. Bornholdt and H. G. Schuster (eds.),
M. E. Newman, S. H. Strogatz and D. J. Watts, ``Random graphs with arbitrary degree distributions and their applications". Phys. Rev. E 64, 026118 (2001).
M. E. Newman, S. H. Strogatz and D. J. Watts, ``Random graph models of social networks", Proc. Natl. Acad. Sci. USA 99, 2566-2572 (2002).
Benjamin and Berger “The diameter of long-range percolation clusters on finite cycles”
Don Coppersmith, David Gamarnik *, Maxim Sviridenko, “The diameter of a long range percolation graph”
Marek Biskup, “Graph diameter in long-range percolation” , “On the scaling of the chemical distance in long-range percolation models”
M. Aizenman, J. Chayes, L. Chayes, C.M. Newman, (1988), Discontinuity of the magnetization in one-dimensional 1 / |x-y|^2 Ising and Potts models, J. Statis. Phys. 50, 1-40. Math. Review 2001c:60151
R. Albert and A.-L.Barabasi. ``Statistical mechanics of complex networks". Reviews of Modern Physics 74, 47 (2002). A.-L.
S.N. Dorogovtsev and J.F.F. Mendes, ``Evolution of networks”, Adv. Phys. 51, 1079-1187 (2002);
M. E. J. Newman, The structure and function of complex networks, SIAM Reviews, 45(2): 167-256, 2003
Duncan J. Watts,, THE "NEW" SCIENCE OF NETWORKS, Annual Review of Sociology Vol. 30: 243-270
M. Mitzenmacher, A Brief History of Generative Models for Power Law and Lognormal Distributions, Internet Mathematics, 2004
A. Albert, H. Jeong, and A.-L. Barabási, Diameter of the World Wide Web, Nature,401, 130-131 (1999)
Albert-Laszlo Barabasi, Reka Albert, Emergence of Scaling in Random Networks, Science,286, 509-512 (1999).
A.-L. Barabasi, Reka Albert, and Hawoong Jeong. Mean-field theory for scale-free random networks. Physica A 272 173-187 (1999).
A.-L. Barabási, R. Albert, H. Jeong, and G. Bianconi, ``Power-law distribution of the World Wide Web", Science, 287, 2115a (2000).
Bernardo A. Huberman, Lada A. Adamic. Growth dynamics of the World-Wide Web. Nature, 399 (1999) 130.
C. Faloutsos, P.
Faloutsos, and M. Faloutsos, “On
power-law relationships of
the internet topology'', ACM SIGCOMM Computer Communication Review, 1999.
G. Siganos, M. Faloutsos, P. Faloutsos, and C.
Faloutsos, "Powerlaws
and the AS-level Internet topology", ACM/IEEE Transactions on
Networking, vol. 11, no. 4, pp. 514-524, Aug. 2003.
Qian Chen, Hyunseok Chang. Ramesh Govindan, Sugih Jamin, Scott J. Shenker, Walter Willinger. The Origin of Power Laws in Internet Topologies Revisited. Proc. of IEEE Infocom 2002.
S.N. Dorogovtsev, J.F.F. Mendes, and A.N. Samukhin, ``Generic scale of the "scale-free" growing networks (Size-dependent degree distribution of a scale-free growing network)", Phys. Rev. E 63, 062101 1-4 (2001); cond-mat/0011115.
Noam Berger, Christian Borgs, Jennifer Chayes, Raissa D'Souza, and Robert Kleinberg. Competition-Induced Preferential Attachment. To appear in Combinatorics, Probability, and Computing. Extended abstract appeared in Proceedings of the 31st International Colloquium on Automata, Languages, and Programming (ICALP 2004), pages 208-221.
S. Yook, H. Jeong, A.-L. Barabasi, “Modeling the Internet’s large-scale topology”, Proceedings of the National Academy of Sciences, 99:13382-13386, 2002.
A. Lakhina, J. W. Byers, M. Crovella,
G. Siganos, M. Faloutsos, P. Faloutsos, C. Faloutsos, ``Power-Laws and the
AS-level Internet Topology", IEEE/ACM Transactions on Networking, 2003.
M. Mihail, C. Papadimitriou, and A. Saberi , On Certain Connectivity
Properties of the Internet Topology, FOCS 2003.
Nadav Eiron and Kevin S. McCurley, Link Structure of Hierarchical Information Networks, Proc. Third Workshop on Algorithms and Models for the Web-Graph (WAW 2004), Lecture Notes in Computer Science, 2004.
Lun Li (CalTech), David Alderson (CalTech), Walter Willinger (AT&T Labs--Research), John Doyle (CalTech), A First-Principles Approach to Understanding the Internet's Router-level Topology, SIGCOMM’04.
Michael T. Gastner and M. E. J.
Newman, The spatial
structure of networks, submitted to Phys. Rev. E.
L. Adamic, R. Lukose, B. Huberman and A. Puniyani, ``Search in Power-Law Networks", Phys. Rev. E, 64 46135 (2001).
C. Gkantsidis, M. Mihail, and A. Saberi, “Hybrid Search Schemes for Unstructured Peer-to-Peer Networks'', accepted to appear in INFOCOM 2005
C. Gkantsidis, M. Mihail, and A. Saberi, “On the Random Walk method in Peer-to-Peer Networks'', INFOCOM 04.
F. Menczer. ``Growing and Navigating the Small World Web by Local Content". Proc. Natl. Acad. Sci. USA 99(22): 14014-14019, 2002
A. Arenas, A. Cabrales, A. Diaz-Guilera, R. Guimera and F. Vega-Redondo, ``Search and Congestion in Complex Networks", [cond-mat/0301124].
C. Gkantsidis, M. Mihail, and A. Saberi, “Conductance and Congestion in Power Law Graphs'', SIGMETRICS 2003.
“Edge Congestion and Topological Properties of Crossed Cubes”, Parallel and Distributed Systems, Jan. 2000 (Vol. 11, No. 1). Abstract
“Edge Congestion of Shortest Path Systems for All-to-All Communication”, Parallel and Distributed Systems, Oct. 1997 (Vol. 8, No. 10). Abstract
J. Gao and L. Zhang, ``Tradeoffs between Stretch Factor and Load Balancing Ratio in Routing on Growth Restrict Graphs'', PODC'04.
Xu, J., Kumar, A., and Yu, X., ``On the Fundamental
Tradeoffs between Routing Table Size and Network Diameter in Peer-to-Peer
Networks'', IEEE Journal on Selected Areas in Communications, vol 22, no 1, pp. 151--163, Jan 2004.
M. Heydemann, J. Meyer, and D. Stotteau, "On forwarding indices of networks", Discrete Applied Math, 23:103-123,
1989.
S. Cicerone G. Di Stefano and M. Flammini, “Static and Dynamic Low-Congested Interval Routing Schemes”.
S. Cicerone G. Di Stefano and M. Flammini, “Low-Congested Interval Routing Schemes for Hypercube-Like Networks”.
I. Abraham and D. Malkhi, “Compact Routing on
Euclidean Metrics'', PODC'04.
C. Gavoille. ``Routing in distributed networks: overview and open problems". ACM SIGACT News - Distributed Computing Column, 32(1):36--52, Mar. 2001.
Brian Towles, William J. Dally, Stephen Boyd ``Throughput-Centric Routing Algorithm
Design (2003) `` SPAA’03
H. Chan, A. Gupta, B. Maggs, and S. Zhou, ``On hierarchical routing in
doubling
metrics'' in Proc. of ACM Symp. on Discrete Algorithms (SODA), 2005.
Kleinrock, L. and F. Kamoun, "Hierarchical Routing for Large Networks, Performance Evaluation and Optimization", Computer Networks, Vol. 1, No. 3, pp. 155-174, January 1977. PDF
Kleinrock, L. and F. Kamoun, "Optimal Clustering
Structures for Hierarchical Topological Design of Large Computer
Networks", Networks, Vol. 10, No. 3, pp. 221-248, Fall 1980. PDF
Ron Banner and Ariel Orda, " Multipath Routing Algorithms for Congestion Minimization", NETWORKING’2005.
N.G. Duffield, P. Goyal, A. Greenberg, P. Mishra, K.K.
Ramakrishnan, J. van der Merwe, “A Flexible
Model for Resource Management in Virtual Private Networks”, SIGCOMM’1999.
A. Gupta, J. Kleinberg, A. Kumar, R. Rastogi, B. Yener. Provisioning a virtual private network: A network design problem for multicommodity flow. Proc. 33rd ACM Symposium on Theory of Computing, 2001.
Cisco - ``Intranet and Extranet Virtual Private
Networking'',\\
http://www.cisco.com/warp/public/cc/so/neso/vpn/vpnsp/ievpn\_rg.htm
E. Ng and H. Zhang, ``Predicting Internet network distance with coordinates-based
approaches", SPAA'02.
B.M. Waxman . ``Routing of multipoint connections". IEEE Journal of Selected Areas in Communications, p. 1617-1622, 1988.
R. Guimera, A. Diaz-Guilera, F. Vega-Redondo, A. Cabrales and A. Arenas, ``Optimal network topologies for local search with congestion", Physical Review Letters (89) 2002.
I. Abraham, D. Malkhi and O. Dobzinski, ``LAND: Stretch
($1+\epsilon$)
Locality-aware Networks for DHTs'', SODA'04.
Xu, J., Kumar, A., and Yu, X., ``On the Fundamental Tradeoffs between Routing Table Size and Network Diameter in Peer-to-Peer Networks'', IEEE Journal on Selected Areas in Communications, vol 22, no 1, pp. 151--163, Jan 2004.
K. P. Gummadi, R. Gummadi, S. D. Gribble, S. Ratnasamy, S. Shenker, and I. Stoica, “The Impact of DHT Routing Geometry on Resilience and Proximity”, In Proceedings of the ACM SIGCOMM 2003.
D. Loguinov, A. Kumar, V. Rai, and
D. Malkhi, M. Naor, D. Ratajczak, ``Viceroy: A Scalable and Dynamic Emulation of the Butterfly", Proc. 21st ACM Symp. on Princ. of Dist. Comp., p. 183-192.
I. Stoica, R. Morris, D. Karger, F. Kaashoek, H. Balakrishnan, ``Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications". ACM SIGCOMM, 2001.
B. Y. Zhao, J. D. Kubiatowicz, A. D. Joseph, ``Tapestry: An Infrastructure for Fault-Tolerant Wide-Area Location and Routing". UC Berkeley Computer Science Division, Report No. UCB/CSD 01/1141, April 2001.
S. Ratnasamy, P. Francis, M. Handley, R. Karp, S. Shenker, ``A Scalable Content-Addressable Network". ACM SIGCOMM, 2001.
S. Ratnasamy, S. Shenker and
Peer-to-Peer Systems (IPTPS), 2002.
A. Rowstron, P. Druschel. ``Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems". 18th IFIP/ACM International Conference on Distributed Systems Platforms (Middleware 2001).
A. Slivkins, “Distance Estimation and Object Location via Rings of Neighbors”, to appear in PODC 2005.
D. Karger and M. Ruhl, ``Finding
Nearest Neighbors in Growth-restricted Metrics'', STOC'02.
E. Ng and H. Zhang, ``Predicting
Internet network distance with coordinates-based approaches", SPAA'02.
S. Arya, G. Das, D. Mount, J.
Salowe, and M. Smid, "Euclidean spanners: short, thin, and lanky,"
in Proc. 27th ACM STOC, 1995, pp. 489--498.
Hubert T-H. Chan, Anupam Gupta,
Bruce M. Maggs, and Shuheng Zhou “On
Hierarchical Routing in Doubling Metrics”; SODA’ 05
Pankaj K. Agarwal, Yusu Wang, and
Peng Yin “Lower Bound for
Sparse Euclidean Spanners”, SODA’05.
Guy Kortsarz , David Peleg, ``Approximating
shallow-light trees”, Proceedings of SoDA’97, p.103-110.
E. Althaus,
S. Funke, S. Har-Peled, J. Konemann, E. Ramos and
M. Skutella, “Approximating
k-Hop Minimum-Spanning Trees”
J. Ho, D. Lee and C. Chang, “Bounded diameter minimum spanning trees and related problems”, ACM-SCG’89
M. Marathe, R. Ravi, R. Sundaram, S. Ravi, D. Rosenkrantz and H. Hunt III, “Bicriteria Network Design Problems”, ICALP’95
Rina Panigrahy “Efficient Hashing
with Lookups in Two Memory Accesses”, SODA’05
Y. Azar, A. Broder, A. Karlin, E. Upfal., “Balanced allocation”, Proc. of 26th STOC (1994), 593-602.
John Byers and Michael Mitzenmacher “Simple Load Balancing for Distributed Hash Tables”, IPTPS’03
Berthold Vöcking , “How asymmetry helps load balancing”,
FOCS’99.
A. Broder and M. Mitzenmacher, “Using
Multiple Hash Functions to Improve IP Lookups”, IEEE INFOCOM 2001, Abstract
and
Conference version (ps)
J. Kleinberg, R. Rubinfeld. Short paths in expander graphs. Proc. 37th IEEE Symposium on Foundations of Computer Science, 1996
Colin Cooper, Alan M. Frieze, Crawling on web graphs. STOC 2002: 419-427
Colin Cooper, Alan M. Frieze: A general model of web graphs. Random Struct. Algorithms 22(3): 311-335 (2003)
Colin Cooper, Alan
M. Frieze: The cover time of sparse random graphs. SODA
2003: 140-147
Andrei Z. Broder, Alan M. Frieze, Eli Upfal: Existence and Construction of Edge-Disjoint Paths on Expander Graphs. SIAM J. Comput. 23(5): 976-989 (1994)
Andrei Z. Broder, Alan M. Frieze, Eli Upfal: Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach. Random Struct. Algorithms 14(1): 87-109 (1999)
P. Gupta and P.Kumar, “The capacity of wireless networks”, IEEE Trans. on Information Theory, Mar 2000.
P Crescenzi, V Kann, M Halldrsson, M Karpinski, “A compendium of NP optimization problems”
NIST, Dictionary of Algorithms and Data Structures.
Aspnes et al. , On-line routing of virtual circuits with applications to load balancing and J. machine scheduling
Baruch Awerbuch, Yossi Azar, Amos Fiat, “Packet Routing via Min-Cost Circuit Routing” (1996)
Baruch Awerbuch, Yossi Azar, Serge Plotkin, Throughput-Competitive On-Line Routing FOCS 1993.
S.N. Dorogovtsev, J.F.F. Mendes, A.N. Samukhin, “Principles of statistical mechanics of random networks”.
Google
queries.
optimal bandwidth virtual path STOC
Awerbuch-Azar-Plotkin FOCS 93 cost benefit for virtual circuits