Sun, 27 Jul 2008 06:07:53 BST CiteULike: Kwisatz's library [19 articles] http://www.citeulike.org/user/Kwisatz CiteULike.org en-gb Copyright © 2004-2008 citeulike.org http://www.citeulike.org/user/Kwisatz/article/155 <i>(25 March 2003)</i><br /><br />Inspired by empirical studies of networked systems such as the Internet, social networks, and biological networks, researchers have in recent years developed a variety of techniques and models to help us understand or predict the behavior of these systems. Here we review developments in this field, including such concepts as the small-world effect, degree distributions, clustering, network correlations, random graph models, models of network growth and preferential attachment, and dynamical processes taking place on networks. The structure and function of complex networks MEJ Newman (25 March 2003) 2004-11-22T00:17:30-00:00 2003 small social world http://www.citeulike.org/user/Kwisatz/article/219664 <i>(13 October 2003)</i><br /><br />Networks created and maintained by social processes, such as the human friendship network and the World Wide Web, appear to exhibit the property of navigability: namely, not only do short paths exist between any pair of nodes, but such paths can easily be found using only local information. It has been shown that for networks with an underlying metric, algorithms using only local information perform extremely well if there is a power-law distribution of link lengths. However, it is not clear why or how real networks might develop this distribution. In this paper we define a decentralized “rewiring” process, inspired by surfers on the Web, in which each surfer attempts to travel from their home page to a random destination, and updates the outgoing link from their home page if this journey takes too long. We show that this process does indeed cause the link length distribution to converge to a power law, achieving a routing time of O(log^2 n) on networks of size n. We also study finite-size effects on the optimal exponent, and show that it converges polylogarithmically slowly as the lattice size goes to infinity. How Do Networks Become Navigable? Aaron Clauset Cristopher Moore (13 October 2003) 2005-06-04T17:11:22-00:00 2003 navigability small world http://www.citeulike.org/user/Kwisatz/article/2197822 <i>(10 Oct 2007)</i><br /><br />We demonstrate that the self-similarity of some scale-free networks with respect to a simple degree-thresholding renormalization scheme finds a natural interpretation in the assumption that network nodes exist in hidden metric spaces. Clustering, i.e., cycles of length three, plays a crucial role in this framework as a topological reflection of the triangle inequality in the hidden geometry. We prove that a class of hidden variable models with underlying metric spaces are able to accurately reproduce the self-similarity properties that we measured in the real networks. Our findings indicate that hidden geometries underlying these real networks are a plausible explanation for their observed topologies and, in particular, for their self-similarity with respect to the degree-based renormalization. Self-similarity of complex networks and hidden metric spaces Angeles Serrano Dmitri Krioukov Marian Boguna (10 Oct 2007) 2008-01-05T19:09:07-00:00 2007 community forwarding small world http://www.citeulike.org/user/Kwisatz/article/1624269 <i>(3 Sep 2007)</i><br /><br />Targeted or quasi-targeted propagation of information is a fundamental process running in complex networked systems. Optimal communication in a network is easy to achieve if all its nodes have a full view of the global topological structure of the network. However many complex networks manifest communication efficiency without nodes having a full view of the network, and yet there is no generally applicable explanation of what mechanisms may render efficient such communication in the dark. In this work we model this communication as an oblivious routing process greedily operating on top of a network and making its decisions based only on distances within a hidden metric space lying underneath. Abstracting intrinsic similarities among networked elements, this hidden metric space is not easily reconstructible from the visible network topology. Yet we find that the structure of complex networks observed in reality, characterized by strong clustering and specific values of exponents of power-law degree distributions, maximizes their navigability, i.e., the efficiency of the greedy path-finding strategy in this hidden framework. We explain this observation by showing that more navigable networks have more prominent hierarchical structures which are congruent with the optimal layout of routing paths through a network. This finding has potentially profound implications for constructing efficient routing and searching strategies in communication and social networks, such as the Internet, Web, etc., and merits further research that would explain whether navigability of complex networks does indeed follow naturally from specifics of their evolution. Navigability of Complex Networks M Boguna D Krioukov KC Claffy (3 Sep 2007) 2007-09-05T14:26:14-00:00 2007 forwardingnetworks small world http://www.citeulike.org/user/Kwisatz/article/2083576 <i>INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE (2007), pp. 848-856.</i> The Cache Inference Problem and its Application to Content and Request Routing N Laoutaris G Zervas A Bestavros G Kollios INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE (2007), pp. 848-856. 2007-12-09T20:33:05-00:00 2007 INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE 848 856 no-tag http://www.citeulike.org/user/Kwisatz/article/1932063 <i></i> Towards a Theory of Scale-Free Graphs: Definition, Properties and Implications Lun 2007-11-18T03:53:21-00:00 scale-free willinger http://www.citeulike.org/user/Kwisatz/article/488868 <i>Vol. 2692 (May 2003), pp. 1-16.</i><br /><br />Trust is an essential component of successful interactions in social life as well as in business relationships. In this paper we propose a system that closely reflects real-world trust building in an online environment. We describe the models used to represent trust in entities in various categories, algorithms to calculate and update trust based on experiences of entities with each other and the agent interactions necessary for finding and exchanging trust information. Architecture and Algorithms for a Distributed Reputation System M Kinateder K Rothermel Vol. 2692 (May 2003), pp. 1-16. 2006-02-01T19:43:08-00:00 2003 2692 1 16 Springer-Verlag reputation systems http://www.citeulike.org/user/Kwisatz/article/350511 <i>Commun. ACM, Vol. 43, No. 12. (December 2000), pp. 45-48.</i> Reputation systems Paul Resnick Ko Kuwabara Richard Zeckhauser Eric Friedman doi:10.1145/355112.355122 Commun. ACM, Vol. 43, No. 12. (December 2000), pp. 45-48. 2005-10-14T09:00:19-00:00 2000 Commun. ACM 0001-0782 43 12 45 48 ACM Press reputation systems http://www.citeulike.org/user/Kwisatz/article/1603536 <i>(2007), pp. 717-726.</i> A framework for community identification in dynamic social networks Chayant Tantipathananandh Tanya Berger-Wolf David Kempe doi:10.1145/1281192.1281269 (2007), pp. 717-726. 2007-08-29T05:25:04-00:00 2007 717 726 ACM Press community detection kempe social http://www.citeulike.org/user/Kwisatz/article/1932001 <i>(2007), pp. 4-5.</i> Challenges in mining social network data: processes, privacy, and paradoxes Jon Kleinberg doi:10.1145/1281192.1281195 (2007), pp. 4-5. 2007-11-18T03:20:04-00:00 2007 4 5 ACM kleinberg networks privacy social http://www.citeulike.org/user/Kwisatz/article/1931618 <i>(2007), pp. 32-40.</i> Social network analysis for routing in disconnected delay-tolerant MANETs Elizabeth Daly Mads Haahr doi:10.1145/1288107.1288113 (2007), pp. 32-40. 2007-11-18T00:52:48-00:00 2007 32 40 ACM forwarding networks psn social http://www.citeulike.org/user/Kwisatz/article/1266960 <i>(2005), pp. 217-228.</i> Mining anomalies using traffic feature distributions Anukool Lakhina Mark Crovella Christophe Diot doi:10.1145/1080091.1080118 (2005), pp. 217-228. 2007-04-30T00:27:40-00:00 2005 217 228 ACM Press crovella diot lakhina http://www.citeulike.org/user/Kwisatz/article/1875559 <i>INFOCOM 2006. 25th IEEE International Conference on Computer Communications. Proceedings (2006), pp. 1-13.</i> Impact of Human Mobility on the Design of Opportunistic Forwarding Algorithms A Chaintreau P Hui J Crowcroft C Diot R Gass J Scott doi:10.1109/INFOCOM.2006.172 INFOCOM 2006. 25th IEEE International Conference on Computer Communications. Proceedings (2006), pp. 1-13. 2007-11-06T23:32:21-00:00 2006 INFOCOM 2006. 25th IEEE International Conference on Computer Communications. Proceedings 1 13 chaintreau crowcroft diot http://www.citeulike.org/user/Kwisatz/article/149353 <i>(2003), pp. 301-312.</i> An information-theoretic approach to traffic matrix estimation Yin Zhang Matthew Roughan Carsten Lund David Donoho doi:10.1145/863955.863990 (2003), pp. 301-312. 2005-04-04T18:42:22-00:00 2003 301 312 ACM Press donoho roughan zhang http://www.citeulike.org/user/Kwisatz/article/1875513 <i>(2002), pp. 161-174.</i> Traffic matrix estimation: existing techniques and new directions A Medina N Taft K Salamatian S Bhattacharyya C Diot doi:10.1145/633025.633041 (2002), pp. 161-174. 2007-11-06T23:11:10-00:00 2002 0146-4833 161 174 ACM diot medina taft http://www.citeulike.org/user/Kwisatz/article/1452891 <i>IEEE/ACM Trans. Netw., Vol. 3, No. 3. (June 1995), pp. 226-244.</i> Wide area traffic: the failure of Poisson modeling Vern Paxson Sally Floyd doi:10.1109/90.392383 IEEE/ACM Trans. Netw., Vol. 3, No. 3. (June 1995), pp. 226-244. 2007-07-12T19:27:37-00:00 1995 IEEE/ACM Trans. Netw. 1063-6692 3 3 226 244 IEEE Press floyd paxson http://www.citeulike.org/user/Kwisatz/article/250460 <i>IEEE/ACM Trans. Netw., Vol. 2, No. 1. (February 1994), pp. 1-15.</i> On the self-similar nature of Ethernet traffic (extended version) Will Leland Murad Taqqu Walter Willinger Daniel Wilson doi:10.1109/90.282603 IEEE/ACM Trans. Netw., Vol. 2, No. 1. (February 1994), pp. 1-15. 2005-07-09T04:18:15-00:00 1994 IEEE/ACM Trans. Netw. 1063-6692 2 1 1 15 IEEE Press taqqu willinger http://www.citeulike.org/user/Kwisatz/article/232997 <i>Vol. 32, No. 1. (June 2004), pp. 61-72.</i> Structural analysis of network traffic flows Anukool Lakhina Konstantina Papagiannaki Mark Crovella Christophe Diot Eric Kolaczyk Nina Taft doi:10.1145/1005686.1005697 Vol. 32, No. 1. (June 2004), pp. 61-72. 2005-06-21T00:07:19-00:00 2004 0163-5999 32 1 61 72 ACM Press lakhina taft http://www.citeulike.org/user/Kwisatz/article/1875488 <i></i> Diversity of Forwarding Paths in Pocket Switched Networks 2007-11-06T23:00:09-00:00 chaintreau crovella diot erramilli