{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,30]],"date-time":"2025-01-30T06:05:49Z","timestamp":1738217149330,"version":"3.34.0"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540770954"},{"type":"electronic","value":"9783540770961"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-77096-1_20","type":"book-chapter","created":{"date-parts":[[2008,4,11]],"date-time":"2008-04-11T11:44:46Z","timestamp":1207914286000},"page":"274-285","source":"Crossref","is-referenced-by-count":1,"title":["Non-Searchability of Random Power-Law Graphs"],"prefix":"10.1007","author":[{"given":"Philippe","family":"Duchon","sequence":"first","affiliation":[]},{"given":"Nicole","family":"Eggemann","sequence":"additional","affiliation":[]},{"given":"Nicolas","family":"Hanusse","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"20_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., Gavoille, C.: Object location using path separators. In: ACM Symp. on Principles of Distributed Computing (PODC), pp. 188\u2013197 (2006)","DOI":"10.1145\/1146381.1146411"},{"issue":"046135","key":"20_CR2","first-page":"1","volume":"64","author":"L. Adamic","year":"2001","unstructured":"Adamic, L., Lukose, R., Puniyani, A., Huberman, B.: Search in power law networks. Physical Reviews E\u00a064(046135), 1\u20138 (2001)","journal-title":"Physical Reviews E"},{"key":"20_CR3","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1145\/335305.335326","volume-title":"STOC 2000: Proceedings of the thirty-second annual ACM symposium on Theory of computing","author":"W. Aiello","year":"2000","unstructured":"Aiello, W., Chung, F., Lu, L.: A random graph model for massive graphs. In: STOC 2000: Proceedings of the thirty-second annual ACM symposium on Theory of computing, pp. 171\u2013180. ACM Press, New York (2000)"},{"issue":"5439","key":"20_CR4","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"A.-L. Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si, A.-L., Albert, R.: Emergence of scaling in random networks. Science\u00a0286(5439), 509\u2013512 (1999)","journal-title":"Science"},{"key":"20_CR5","first-page":"1","volume-title":"Handbook of graphs and networks","author":"B. Bollob\u00e1s","year":"2003","unstructured":"Bollob\u00e1s, B., Riordan, O.: Mathematical results on scale-free random graphs. In: Handbook of graphs and networks, pp. 1\u201334. Wiley-VCH, Berlin (2003)"},{"issue":"1","key":"20_CR6","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/s00493-004-0002-2","volume":"24","author":"B. Bollob\u00e1s","year":"2004","unstructured":"Bollob\u00e1s, B., Riordan, O.: The diameter of a scale-free random graph. Combinatorica\u00a024(1), 5\u201334 (2004)","journal-title":"Combinatorica"},{"issue":"3","key":"20_CR7","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1002\/rsa.1009","volume":"18","author":"B. Bollob\u00e1s","year":"2001","unstructured":"Bollob\u00e1s, B., Riordan, O., Spencer, J., Tusn\u00e1dy, G.: The degree sequence of a scale-free random graph process. Random Structures and Algorithms\u00a018(3), 279\u2013290 (2001)","journal-title":"Random Structures and Algorithms"},{"issue":"1-3","key":"20_CR8","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.disc.2003.10.020","volume":"282","author":"P.G. Buckley","year":"2004","unstructured":"Buckley, P.G., Osthus, D.: Popularity based random graph models leading to a scale-free degree sequence. Discrete Mathematics\u00a0282(1-3), 53\u201368 (2004)","journal-title":"Discrete Mathematics"},{"key":"20_CR9","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/PL00012580","volume":"6","author":"F. Chung","year":"2002","unstructured":"Chung, F., Lu, L.: Connected components in random graphs with given degree sequences. Annals of Combinatorics\u00a06, 125\u2013145 (2002)","journal-title":"Annals of Combinatorics"},{"issue":"1","key":"20_CR10","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1080\/15427951.2004.10129081","volume":"1","author":"F. Chung","year":"2003","unstructured":"Chung, F., Lu, L.: The average distance in random graphs with given expected degrees. Internet Mathematics\u00a01(1), 91\u2013114 (2003)","journal-title":"Internet Mathematics"},{"issue":"2","key":"20_CR11","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1137\/050630106","volume":"20","author":"F. Chung","year":"2006","unstructured":"Chung, F., Lu, L.: The volume of the giant component of a random graph with given expected degrees. SIAM J. Discret. Math.\u00a020(2), 395\u2013411 (2006)","journal-title":"SIAM J. Discret. Math."},{"issue":"3","key":"20_CR12","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1002\/rsa.10084","volume":"22","author":"C. Cooper","year":"2003","unstructured":"Cooper, C., Frieze, A.M.: A general model of web graphs. Random Struct. Algorithms\u00a022(3), 311\u2013335 (2003)","journal-title":"Random Struct. Algorithms"},{"issue":"3","key":"20_CR13","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1080\/15427951.2005.10129105","volume":"2","author":"C. Cooper","year":"2005","unstructured":"Cooper, C., Klasing, R., Zito, M.: Lower bounds and algorithms for dominating sets in web graphs. Internet Mathematics\u00a02(3), 275\u2013300 (2005)","journal-title":"Internet Mathematics"},{"key":"20_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/rsa.3240070102","volume":"6","author":"L. Devroye","year":"1995","unstructured":"Devroye, L., Lu, J.: The strong convergence of maximal degrees in uniform random recursive trees and dags. Random Structures and Algorithms\u00a06, 1\u201314 (1995)","journal-title":"Random Structures and Algorithms"},{"issue":"21","key":"20_CR15","doi-asserted-by":"publisher","first-page":"4633","DOI":"10.1103\/PhysRevLett.85.4633","volume":"85","author":"S.N. Dorogovtsev","year":"2000","unstructured":"Dorogovtsev, S.N., Mendes, J.F., Samukhin, A.N.: Structure of growing networks with preferential linking. Physical Review Letters\u00a085(21), 4633\u20134636 (2000)","journal-title":"Physical Review Letters"},{"key":"20_CR16","unstructured":"Drinea, E., Enachescu, M., Mitzenmacher, M.: Variations on random graph models for the web. Technical report, Harvard U., Dept. of Computer Science (2001)"},{"issue":"1","key":"20_CR17","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.tcs.2005.12.008","volume":"355","author":"P. Duchon","year":"2006","unstructured":"Duchon, P., Hanusse, N., Lebhar, E., Schabanel, N.: Could any graph be turned into a small-world? Theor. Comput. Sci.\u00a0355(1), 96\u2013103 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"20_CR18","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1145\/1148109.1148145","volume-title":"SPAA","author":"P. Duchon","year":"2006","unstructured":"Duchon, P., Hanusse, N., Lebhar, E., Schabanel, N.: Towards small world emergence. In: Gibbons, P.B., Vishkin, U. (eds.) SPAA, pp. 225\u2013232. ACM Press, New York (2006)"},{"key":"20_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"791","DOI":"10.1007\/11561071_70","volume-title":"Algorithms \u2013 ESA 2005","author":"P. Fraigniaud","year":"2005","unstructured":"Fraigniaud, P.: Greedy routing in tree-decomposed graphs. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 791\u2013802. Springer, Heidelberg (2005)"},{"key":"20_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1163","DOI":"10.1007\/11549468_127","volume-title":"Euro-Par 2005 Parallel Processing","author":"P. Fraigniaud","year":"2005","unstructured":"Fraigniaud, P., Gauron, P., Latapy, M.: Combining the use of clustering and scale-free nature of user exchanges into a simple and efficient p2p system. In: Cunha, J.C., Medeiros, P.D. (eds.) Euro-Par 2005. LNCS, vol.\u00a03648, pp. 1163\u20131172. Springer, Heidelberg (2005)"},{"key":"20_CR21","doi-asserted-by":"crossref","unstructured":"Kim, B.J., Han, C.N.Y.S.K., Jeong, H.: Path finding strategies in scale-free networks. Physical Review E, 65(0227103) (2002)","DOI":"10.1103\/PhysRevE.65.027103"},{"key":"20_CR22","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.: The small-world phenomenon: An algorithmic perspective. In: Proceedings of the ACM Symposium on Theory of Computing (STOC), pp. 163\u2013170 (2000)","DOI":"10.1145\/335305.335325"},{"key":"20_CR23","unstructured":"Kleinberg, J.: Complex networks and decentralized search algorithms. In: Proceedings of the International Congress of Mathematicians (ICM) (2006)"},{"key":"20_CR24","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/S0375-9601(02)01317-8","volume":"303","author":"Z. Li","year":"2002","unstructured":"Li, Z., Lai, Y.-C., Ye, N., Dasgupta, P.: Connectivity distribution and attack tolerance of general networks with both preferential and random attachments. Physics Letters A\u00a0303, 337\u2013344 (2002)","journal-title":"Physics Letters A"},{"issue":"2-3","key":"20_CR25","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1002\/rsa.3240060204","volume":"6","author":"M. Molloy","year":"1995","unstructured":"Molloy, M., Reed, B.: A critical point for random graphs with a given degree sequence. Random Structures and Algorithms\u00a06(2-3), 161\u2013179 (1995)","journal-title":"Random Structures and Algorithms"},{"key":"20_CR26","first-page":"143","volume":"39","author":"T.F. Mri","year":"2003","unstructured":"Mri, T.F.: On random trees. Studia Sci. Math. Hungar.\u00a039, 143\u2013155 (2003)","journal-title":"Studia Sci. Math. Hungar."},{"key":"20_CR27","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1017\/S0963548304006133","volume":"14","author":"T.F. Mri","year":"2005","unstructured":"Mri, T.F.: The maximum degree of the Barabsi-Albert random tree. Combinatorics, Probability and Computing\u00a014, 339\u2013348 (2005)","journal-title":"Combinatorics, Probability and Computing"},{"key":"20_CR28","unstructured":"Nguyen, V., Martel, C.: Analyzing and characterizing small-world graphs. In: SODA 2005: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 311\u2013320."},{"key":"20_CR29","doi-asserted-by":"crossref","unstructured":"Sarshar, N., Boykin, O., Roychowdhury, V.P.: Percolation search in power law networks: Making unstructured peer-to-peer networks scalable. In: Proc. of the IEEE International Conference on Peer-to-Peer Computing (P2P 2004), pp. 2\u20139 (2004)","DOI":"10.1109\/PTP.2004.1334925"},{"key":"20_CR30","doi-asserted-by":"crossref","unstructured":"Slivkins, A.: Distance estimation and object location via rings of neighbors. In: 24 th ACM Symp. on Principles of Distributed Computing (PODC), pp. 41\u201350 (2005)","DOI":"10.1145\/1073814.1073823"},{"key":"20_CR31","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1016\/j.physa.2005.01.036","volume":"353","author":"X. Yao","year":"2005","unstructured":"Yao, X., Zhang, C.-S., Chen, J.-W., Li, Y.-D.: On the formation of degree and cluster-degree correlations in scale-free networks. Physica A\u00a0353, 661\u2013673 (2005)","journal-title":"Physica A"}],"container-title":["Lecture Notes in Computer Science","Principles of Distributed Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77096-1_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,29]],"date-time":"2025-01-29T16:41:29Z","timestamp":1738168889000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77096-1_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540770954","9783540770961"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77096-1_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}