Small world networks

 

Newman M. E. J. [2000], "Models of the Small World: A Review", Working Paper

http://tanzeem.www.media.mit.edu/people/tanzeem/cohn/CoHN.htm

It is believed that almost any pair of people in the world can be connected to one another by a short chain of intermediate acquaintances, of typical length about six. This phenomenon, colloquially referred to as the “six degrees of separation,” has been the subject of considerable recent interest within the physics community. This paper provides a short review of the topic.

 

"Six degrees of separation" :there is a path of no more than six acquaintances linking any human being to any other being on the planet. While the exact number six may not be universal, it does appear that for most social networks, only a short chain is needed to connect even the most distant of the network's members. This observation has immediate consequences for the spread of disease and evolutionary game theory, as well as related topics concerning genetic regulatory networks and networks of synchronized oscillators. At first sight this does not seem too surprising a result; random networks have average vertex-vertex distances which increase as the logarithm of the number of vertices and which can therefore be small even in very large networks. However, real social networks are far from random, possessing well-defined locales in which the probability of connection is high and the probability of a connection between two vertices chosen at random is very low.

Watts and Strogatz have recently proposed a model of the ``small world" which reconciles these observations. Their model does indeed possess well-defined locales, with vertices falling on a regular lattice, but in addition there is a fixed density of random "shortcuts" on the lattice which can link distant vertices. Their principal finding is that only a small density of such shortcuts is necessary to produce vertex-vertex distances comparable to those found on a random network. This suggests the possibility of predicting cluster formation (and hence, information diffusion) by a parameter which measures the extent of random perturbations in connectivity.

Watts, D.J., S. H. Strogatz [1998], "Collective dynamics of 'small-world' networks." Nature, 393:440-442, 1998.

Abstract : Networks of coupled dynamical systems have been used to model biological oscillators1–4, Josephson junction arrays5,6, excitable media7, neural networks8–10, spatial games11, genetic control networks12 and many other self-organizing systems. Ordinarily, the connection topology is assumed to be either completely regular or completely random. But many biological, technological and social networks lie somewhere between these two extremes. Here we explore simple models of networks that can be tuned through this middle ground: regular networks ‘rewired’ to introduce increasing amounts of disorder. We find that these systems can be highly clustered, like regular lattices, yet have small characteristic path lengths, like random graphs. We call them ‘small-world’ networks, by analogy with the small-world phenomenon13,14 (popularly known as six degrees of separation15). The neural network of the worm Caenorhabditis elegans, the power grid of the western United States, and the collaboration graph of film actors are shown to be small-world networks. Models of dynamical systems with small-world coupling display enhanced signal-propagation speed, computational power, and synchronizability. In particular, infectious diseases spread more easily in small-world networks than in regular lattices.

Strogatz S. H. [2001], "Exploring complex networks", Nature 410, 268-276

http://tanzeem.www.media.mit.edu/people/tanzeem/cohn/CoHN.htm

The study of networks pervades all of science, from neurobiology to statistical physics. The most basic issues are structural: how does one characterize the wiring diagram of a food web or the Internet or the metabolic network of the bacterium Escherichia coli? Are there any unifying principles underlying their topology? From the perspective of nonlinear dynamics, we would also like to understand how an enormous network of interacting dynamical systems — be they neurons, power stations or lasers — will behave collectively, given their individual dynamics and coupling architecture. Researchers are only now beginning to unravel the structure and dynamics of complex networks.

 

Milgram, S. "The small world problem." Psychol. Today, 2:60-67, 1967.

Sanjay Jain, Physics, Centre for Theoretical Studies, Indian Institute of Science, Bangalore

Jain S., Krishna S. [2001], "A model for the emergence of cooperation, interdependence and structure in evolving networks", Santa Fe Institute Working Paper

Evolution produces complex and structured networks of interacting components in chemical, biological, and social systems. We describe a simple mathematical model for the evolution of an idealized chemical system to study how a network of cooperative molecular species arises and evolves to become more complex and structured. The network is modeled by a directed weighted graph whose positive and negative links represent `catalytic' and `inhibitory' interactions among the molecular species, and which evolves as the least populated species (typically those that go extinct) are replaced by new ones. A small autocatalytic set (ACS), appearing by chance, provides the seed for the spontaneous growth of connectivity and cooperation in the graph. A highly structured chemical organization arises inevitably as the ACS enlarges and percolates through the network in a short, analytically determined time scale. This self-organization does not require the presence of self-replicating species. The network also exhibits catastrophes over long time scales triggered by the chance elimination of `keystone' species, followed by recoveries.

http://www.santafe.edu/sfi/research/focus/networkDynamics/projects/networkFormation.html

 

Troy Tassier, Filippo Menczer : Santa Fe Institute

Tassier T., Menczer F. [2000], "Emerging Small-World Referral Networks in Evolutionary Labor Markets", Santa Fe Institute Working Paper

We model a labor market that includes referral networks using an agent based simulation. Agents maximize their employment satisfaction by allocating resources to build friendship networks and to adjust search intensity. We use a local selection evolutionary algorithm, which maintains a diverse population of strategies, to study the adaptive graph topologies resulting from the model. The evolved networks display mixtures of regularity and randomness, as in small-world networks. A second characteristic emerges in our model as time progresses; the population loses efficiency due to over-competition for job referral contacts in a way similar to social dilemmas such as the tragedy of the commons. Analysis reveals that the loss of global fitness is driven by an increase in individual robustness, which allows agents to live longer by surviving job losses. The behavior of our model suggests predictions for a number of policies.

 

Cristopher Moore and M. E. J. Newman

Moore C., Newman M.E.J [2000], "Epidemics and Percolation in Small-World Networks", Santa Fe Institute Working Paper

We study some simple models of disease transmission on small-world networks, in which either the probability of infection by a disease or the probability of its transmission is varied, or both. The resulting models display epidemic behavior when the infection or transmission probability rises above the threshold for site or bond percolation on the network, and we give exact solutions for the position of this threshold in a variety of cases. We confirm our analytic results by numerical simulation.

 

Moore C., Newman M.E.J [2000], "Exact solution of site and bond percolation on small-world networks", Santa Fe Institute Working Paper

We study percolation on small-world networks, which has been proposed as a simple model of the propagation of disease. The occupation probabilities of sites and bonds correspond to the susceptibility of individuals to the disease and the transmissibility of the disease respectively. We give an exact solution of the model for both site and bond percolation, including the position of the percolation transition at which epidemic behavior sets in, the values of the two critical exponents governing this transition, and the mean and variance of the distribution of cluster sizes (disease outbreaks) below the transition.

M. Granovetter M. [1973], "The strength of weak ties", American Journal of Sociology, 78(6), 1360-1380 http://tanzeem.www.media.mit.edu/people/tanzeem/cohn/CoHN.htm

Granovetter M. [1978], "Threshold models of collective behavior", American Journal of Sociology, 83(6), 1420-1443.

Moody, J. and D.R. White [2002], "Social Cohesion and Embeddedness: A Hierarchical Conception of Social Groups", American Journal of Sociology (submitted)

http://tanzeem.www.media.mit.edu/people/tanzeem/cohn/CoHN.htm

While questions about social cohesion lie at the core of our discipline, no clear definition of cohesion exists. We present a definition of social cohesion based on network connectivity that leads to an operationalization of social embeddedness. We define cohesiveness as the minimum number of actors who, if removed from a group, would disconnect the group. This definition generates hierarchically nested groups, where highly cohesive groups are embedded within less cohesive groups. We discuss the theoretical implications of this definition and demonstrate the empirical applicability of our conception of nestedness by testing the predicted correlates of our cohesion measure within high school friendship and interlocking directorate networks. Keywords: Social networks, social theory, social cohesion, connectivity algorithm, embeddedness.

 

 

Mahadevan Venkatraman, Yu B., and Munindar P. Singh Department of Computer Science, North Carolina State University

Venkatraman M., Bin Yu, Singh M.P. [2001], "Trust and Reputation Management in a Small-World Network", Working Paper

Successful commerce relies heavily upon the reputations that the different parties acquire through their dealings with each other. We view an e-commerce community as a social network, which supports reputations both for expertise (providing good service) and helpfulness (providing good referrals). We study the small-world phenomena such as the emergence of subcommunities, and pivot vertices (which link different subcommunities) in the social network, and discovered that the quality of the network improves with the presence of a pivot.

 

J. Kleinberg J. [1999], "The small-world phenomenon: An algorithmic perspective", Cornell Computer Science Technical Report, 99-1776, October 1999.

Long a matter of folklore, the "small-world phenomenon" the principle that we are all linked by short chains of acquaintances was inaugurated as an area of experimental study in the social sciences through the pioneering work of Stanley Milgram in the 1960's. This work was among the first to make the phenomenon quantitative, allowing people to speak of the "six degrees of separation" between any two people in the United States. Since then, a number of network models have been proposed as frameworks in which to study the problem analytically. One of the most refined of these models was formulated in recent work of Watts and Strogatz; their framework provided compelling evidence that the small-world phenomenon is pervasive in a range of networks arising in nature and technology, and a fundamental ingredient in the evolution of the World Wide Web. But existing models are insufficient to explain the striking algorithmic component of Milgram's original findings: that individuals using local information are collectively very effective at actually constructing short paths between two points in a social network. Although recently proposed network models are rich in short paths, we prove that no decentralized algorithm, operating with local information only, can construct short paths in these networks with non-negligible probability. We then define an infinite family of network models that naturally generalizes the Watts-Strogatz model, and show that for one of these models, there is a decentralized algorithm capable of finding short paths with high probability. More generally, we provide a strong characterization of this family of network models, showing that there is in fact a unique model within the family for which decentralized algorithms are effective.

 

Gladwell M. [1999], Six degrees of Lois Weisberg, New Yorker, pages 52–63, Jan. 1999. January 11 issue.

Watts D. J., Strogatz S. H. [1998], Collective dynamics of ‘small-world’ networks. Nature, 393:440–442, June 1998.

Yu B., Venkatraman M., Singh M. P.[2000], An adaptive social network for information access: Theoretical and experimental results, Applied Artificial Intelligence, 2000. To appear.

 

Luis A. Nunes Amaral, Antonio Scala, Marc Barthélémy, and H. Eugene Stanley Center for Polymer Studies and Department of Physics Boston University, MA 02215, USA

Amaral, L. A. N., Scala, A., Barthelemy, M., and Stanley, H. E. [2000], "Classes of behavior of small-world networks", Working Paper

http://xxx.lanl.gov/abs/cond-mat/0001458

Small-world networks are the focus of recent interest because they appear to circumvent many of the limitations of either random networks or regular lattices as frameworks for the study of interaction networks of complex systems. Here, we report an empirical study of the statistical properties of a variety of diverse real-world networks. We present evidence of the occurrence of three classes of small-world networks: (a) scale-free networks, characterized by a vertex connectivity distribution that decays as a power law; (b) broad-scale networks, characterized by a connectivity distribution that has a power-law regime followed by a sharp cut-off; (c) single-scale networks, characterized by a connectivity distribution with a fast decaying tail. Moreover, we note for the classes of broad-scale and single-scale networks that there are constraints limiting the addition of new links. Our results suggest that the nature of such constraints may be the controlling factor for the emergence of different classes of networks.

 

Ronald S. Burt Department of Sociology, Graduate School of Business, University of Chicago, Chicago, IL 60637, USA

Burt Ronald S. [2002], "Bridge decay", Social Networks, Volume 24, Issue 4, October 2002.

Abstract : This paper is about three points: network bridges are critical to the advantage known as social capital, bridges relative to other kinds of relationships show faster rates of decay over time, and the faster decay in bridges has implications for the stability of social capital. A bridge connects people not otherwise connected; in other words, it spans a structural hole in the surrounding organization. I have 4 years of data on the social networks of bankers in a large organization. I show that bridge relations are associated with more positive peer reputations and higher compensation, but bridges decay at an alarming rate. Out of 10, 9 bridges this year are gone next year. I describe factors in the rate of decay, find slower decay in the networks of bankers experienced with bridge relationships, and conclude that social capital accrues to those who already have it. An appendix is included on the kinked decay functions observed in contractual bridge relationships. Author Keywords: Change; Structural holes; Social capital; Management; Banking JEL classification codes: C81; J24; J44; J63; M12

 

Frans van Dijk, Joep Sonnemans,  and Frans van Winden CREED Department of Economics, University of Amsterdam, Roetersstraat 11, 1018 WB Amsterdam, The Netherlands

Van Dijk F., Sonnemans J., van Winden F. [2002], "Social ties in a public good experiment", Journal of Public Economics, Volume 85, Issue 2, August 2002, Pages 275-299

Abstract : The formation of social ties is examined in an experimental study of voluntary public good provision. The experimental design consists of three parts. In the first part the value orientation (attitude to a generalized other) is measured. In the second part couples play a multi-period public good game. In the third part the attitudes of subjects to their partners in the public good game is measured. The concept of a social tie is operationalized as the difference between the measurements in the first and third parts. Evidence for the occurrence of social ties is found. These ties depend on the success of the interaction in the public good game. Author Keywords: Public good; Social ties; Experiment JEL classification codes: C91; H41; A13

David Krackhardt, The Heinz School of Public Policy and Management, and The Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, PA, USA

Martin Kilduff, Department of Management and Organization, Smeal College of Business Administration, The Pennsylvania State University, University Park, PA 16802, USA

Krackhardt D., Kilduff M. [2002], "Structure, culture and Simmelian ties in entrepreneurial firms", Social Networks, Volume 24, Issue 3, July 2002, Pages 279-290

Abstract : This article develops a cultural agreement approach to organizational culture that emphasizes how clusters of individuals reinforce potentially idiosyncratic understandings of many aspects of culture including the structure of network relations. Building on recent work concerning Simmelian tied dyads (defined as dyads embedded in three-person cliques), the research examines perceptions concerning advice and friendship relations in three entrepreneurial firms. The results support the idea that Simmelian tied dyads (relative to dyads in general) reach higher agreement concerning who is tied to whom, and who are embedded together in triads in organizations. Author Keywords: Social networks; Simmelian ties; Organizational culture; Cliques; Triads

 

Scale-free networks and Internet topology

 

Réka Albert, Hawoong Jeong and Albert-Laszlo Barabasi, Department of Physics, University of Notre-Dame, Notre Dame, Indiana 46556, USA

Barabasi, A. and Albert, R [1999], "Emergence of scaling in random networks", Science 286, 509-512 http://tanzeem.www.media.mit.edu/people/tanzeem/cohn/CoHN.htm

Systems as diverse as genetic networks or the World Wide Web are best described as networks with complex topology. A common property of many large networks is that the vertex connectivities follow a scale-free power-law distribution. This feature was found to be a consequence of two generic mechanisms: (i) networks expand continuously by the addition of new vertices, and (ii) new vertices attach preferentially to sites that are already well connected. A model based on these two ingredients reproduces the observed stationary scale-free distributions, which indicates that the development of large networks is governed by robust self-organizing phenomena that go beyond the particulars of the individual systems.

 

Barabasi A.L. [2002], Linked: The New Science of Networks, Perseus Publishing, Cambridge, Mass.

 

Albert R., Jeong H., Barabási A.L. [2000], "The Internet's Achilles' heel: error and attack tolerance of complex networks", Nature, 406 378

Barabási A.L., Albert R. [1999], "Emergence of scaling in random networks", Science, 286 509

Bianconi G., Barabási A.L. [2001], "Bose­Einstein condensation in complex networks", Phys. Rev. Lett., 86 5632

Broder A. et al. [2000], "Graph structure in the web", Comput. Netw., 33 309

D S Callaway D.S., et al. [2000], "Network robustness and fragility: percolation on random graphs", Phys. Rev. Lett., 85 5468

Cohen R. et al. [2000], "Resilience of the Internet to random breakdowns", Phys. Rev. Lett., 85 4626

 

 

Michalis Faloutsos U.C. Riverside Dept. of Comp. Science

Petros Faloutsos U. of Toronto Dept. of Comp. Science

Christos Faloutsos Carnegie Mellon Univ. Dept. of Comp. Science

Faloutsos M., Faloutsos P, Faloutsos C [1999], "On power-law relationships of the Internet topology", ACM SIGCOMM Computer Communication Review, Vol. 29, Iss. 4 (October 1999).

Despite the apparent randomness of the Internet, we discover some surprisingly simple power-laws of the Internet topology. These power-laws hold for three snapshots of the Internet, between November 1997 and December 1998, despite a 45% growth of its size during that period. We show that our power-laws fit the real data very well resulting in correlation coefficients of 96% or higher. Our observations provide a novel perspective of the structure of the Internet. The power-laws describe concisely skewed distributions of graph properties such as the node outdegree. In addition, these power-laws can be used to estimate important parameters such as the average neighborhood size, and facilitate the design and the performance analysis of protocols. Furthermore, we can use them to generate and select realistic topologies for simulation purposes.

 

Adamic, L. A., and B.. A. Huberman. "Power-law distribution of the world wide web", Science, 287:2115a, 2000.

S Lawrence and C L Giles 1999 Accessibility of information on the Web Nature 400 107

 

 

Romualdo Pastor-Satorras : Departament de Física i Enginyeria Nuclear, Universitat Politècnica de Catalunya, Campus Nord, Mòdul B4, 08034 Barcelona, Spain

Alessandro Vespignani : The Abdus Salam International Centre for Theoretical Physics (ICTP), P.O. Box 586, 34100 Trieste, Italy

Pastor-Satorras R., Vespignani A. [2001], "Epidemic spreading in scale-free networks", Physical Review Letters, April 2, 2001, Vol. 86, Iss. 14, pp. 3200-3203.

The Internet has a very complex connectivity recently modeled by the class of scale-free networks. This feature, which appears to be very efficient for a communications network, favors at the same time the spreading of computer viruses. We analyze real data from computer virus infections and find the average lifetime and persistence of viral strains on the Internet. We define a dynamical model for the spreading of infections on scale-free networks, finding the absence of an epidemic threshold and its associated critical behavior. This new epidemiological framework rationalizes data of computer viruses and could help in the understanding of other spreading phenomena on communication and social networks.

 

Broder A., Kumar R., Maghoul F., Raghavan P., Rajagopalan S., Stata R. [2000], "Graph structure in the web", 9^th International World Wide Web Conference, Amsterdam, May 15 - 19, 2000.

http://www9.org/w9cdrom/160/160.html

Abstract : The study of the web as a graph is not only fascinating in its own right, but also yields valuable insight into web algorithms for crawling, searching and community discovery, and the sociological phenomena which characterize its evolution.  We report on experiments on local and global properties of the web graph using two Altavista crawls each with over 200 million pages and 1.5 billion links.  Our study indicates that the macroscopic structure of the web is considerably more intricate than suggested by earlier experiments on a smaller scale. Keywords: graph structure, diameter, web measurement

 

D J Watts and S H Strogatz [1998], "Collective dynamics of "small-world" networks", Nature 393440

 

Réka A., Jeong H., Barabasi A.L. [1999], "The diameter of the world wide web", Working Paper,

We use local connectivity measurements to construct a topological model of the www, allowing us to explore and characterize the large scale properties of the web. To determine the local connectivity of the www, we constructed a robot, that adds to its database all URLs found on a document and recursively follows these to retrieve the related documents and URLs.

 

Réka A., Jeong H., Barabasi A.L. [2000], "Topology of evolving networks: local events and universality", Working Paper

Networks grow and evolve by local events, such as the addition of new nodes and links, or rewiring of links from one node to another. We show that depending on the frequency of these processes two topologically different networks can emerge, the connectivity distribution following either a generalized power-law or an exponential. We propose a continuum theory that predicts these two regimes as well as the scaling function and the exponents, in good agreement with the numerical results. Finally, we use the obtained predictions to fit the connectivity distribution of the network describing the professional links between movie actors.

 

Bianconi G., Barabasi A.L. [2000], "Bose-Einstein condensation in complex networks", Working Paper.

The evolution of many complex systems, including the world wide web, business and citation networks is encoded in the dynamic web describing the interactions between the system's constituents. Despite their irreversible and non-equilibrium nature these networks follow Bose statistics and can undergo Bose-Einstein condensation. Addressing the dynamical properties of these non-equilibrium systems within the framework of equilibrium quantum gases predicts that the "first-mover-advantage", "fit-get-rich" and "winner-takes-all" phenomena observed in competitive systems are thermodynamically distinct phases of the underlying evolving networks. PACS numbers: 89.75.Hc, 89.75.-k, 5.65+b

 

Alberto Medina, Anukool Lakhina, Ibrahim Matta, John Byers

Medina A., Matta I., Byers J. [2000], "On the Origin of Power Laws in Internet Topologies", Working Paper

Recent empirical studies [7] have shown that Internet topologies exhibit power laws of the form y = x for the following relationships: (P1) outdegree of node (domain or router) versus rank; (P2) number of nodes versus outdegree; (P3) number of node pairs within a neighborhood versus neighborhood size (in hops); and (P4) eigenvalues of the adjacency matrix versus rank. However, causes for the appearance of such power laws have not been convincingly given. In this paper, we examine four factors in the formation of Internet topologies. These factors are (F1) preferential connectivity of a new node to existing nodes; (F2) incremental growth of the network; (F3) distribution of nodes...

 

Medina A., Matta I., Byers J. [2001], "Universal Topology Generation from a User’s Perspective", Working Paper

Effective engineering of the Internet is predicated upon a detailed understanding of issues such as the large-scale structure of its underlying physical topology, the manner in which it evolves over time, and the way in which its constituent components contribute to its overall function. Unfortunately, developing a deep understanding of these issues has proven to be a challenging task, since it in turn involves solving difficult problems such as mapping the actual topology, characterizing it, and developing models that capture its emergent behavior. Consequently, even though there are a number of topology models, it is an open question as to how representative the topologies they generate are of the actual Internet. Our goal is to produce a topology generation framework which improves the state of the art and is based on design principles which include representativeness, inclusive-ness, and interoperability. Representativeness leads to synthetic topologies that accurately reflect many aspects of the actual Internet topology (e.g. hierarchical structure, degree distribution, etc.). Inclusiveness combines the strengths of as many generation models as possible in a single generation tool. Interoperability provides interfaces to widely-used simulation and visualization applications such as ns and SSF. We call such a tool a universal topology generator. In this paper we discuss the design, implementation and usage of the BRITE universal topology generation tool that we have built. We also describe the BRITE Analysis Engine, BRIANA, which is an independent piece of software designed and built upon BRITE design goals of flexibility and extensibility. The purpose of BRIANA is to act as a repository of analysis routines along with a user–friendly interface that allows its use on different topology formats.

 

Marshall Van Alstyne Erik Brynjolfsson

Brynjolfsson E., Marshall Van Alstyne [1997], "The Net Effect: Modeling and Measuring the Integration of Electronic Communities", Working Paper.

Information technology can link geographically separated people and help them locate interesting or compatible resources. Although these attributes have the potential to bridge gaps and unite communities, they also have the potential to fragment interaction and divide groups by leading people to spend more time on special interests and by screening out less preferred contact. This paper introduces precise measures of information integration and develops a model of individual knowledge profiles and community affiliation. These factors suggest different conditions under which improved access, search, and screening can integrate or fragment interaction. As IT capabilities continue to improve, preferences, not geography or technology, become the key determinants of community boundaries.

 

.

David M. Pennock, GaryW. Flake, Steve Lawrence, Eric J. Glover, C. Lee Giles

Pennock D.M., Flake G.W., Lawrence S., Glover E.J., Giles C.L. [2002], "Winners don’t take all: Characterizing the competition for links on the web", Proceedings of the National Academy of Sciences, Volume 99, Issue 8, pp. 5207–5211, April, 2002.

http://modelingtheweb.com/

As a whole, the World Wide Web displays a striking “rich get richer” behavior, with a relatively small number of sites receiving a disproportionately large share of hyperlink references and traffic. However, hidden in this skewed global distribution, we discover a qualitatively different and considerably less biased link distribution among subcategories of pages—for example, among all university homepages or all newspaper homepages. While the connectivity distribution over the entire web is close to a pure power law, we find that the distribution within specific categories is typically unimodal on a log scale, with the location of the mode, and thus the extent of the “rich get richer” phenomenon, varying across different categories. Similar distributions occur in many other naturally-occurring networks, including research paper citations, movie actor collaborations, and US power grid connections. A simple generative model, incorporating a mixture of preferential and uniform attachment, quantifies the degree to which the rich nodes grow richer, and how new (and poorly-connected) nodes can compete. The model accurately accounts for the true connectivity distributions of category-specific web pages, the web as a whole, and other social networks.

 

William Aiello, Fan Chung, Linyuan Lu

William Aiello W., Chung F., Lu L. [2001], "Random evolution in massive graphs", IEEE Symposium on Foundations of Computer Science.

Abstract : Many massive graphs (such as WWW graphs and Call graphs) share certain universal characteristics which can be described by so called the “power law”. In this paper, we will first briefly survey the history and previous work on power law graphs. Then we will give four evolution models for generating power law graphs by adding one node/edge at a time. We will show that for any given edge density and desired distributions for in-degrees and out-degrees (not necessarily the same, but adhered to certain general conditions), the resulting graph will almost surely satisfy the power law and the in/out-degree conditions. We will show that our most general directed and undirected models include nearly all known models as special cases. In addition, we consider another crucial aspects of massive graphs that is called “scale-free” in the sense that the frequency of sampling (w.r.t. the growth rate) is independent of the parameter of the resulting power law graphs. We will show that our evolution models generate scale-free power law graphs1.

 

 

Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins, IBM Almaden Research Center K53, 650 Harry Road, San Jose, CA 95120, USA.

Kumar R., Raghavan P., Rajagopalan S., Tomkins A. [1999], "Trawling the web for emerging cyber-communities", Working Paper, IBM Almaden Research Center

Abstract: : The web harbors a large number of communities -- groups of content-creators sharing a common interest -- each of which manifests itself as a set of interlinked web pages. Newgroups and commercial web directories together contain of the order of 20000 such communities; our particular interest here is on emerging communities -- those that have little or no representation in such fora. The subject of this paper is the systematic enumeration of over 100,000 such emerging communities from a web crawl: we call our process trawling. We motivate a graph-theoretic approach to locating such communities, and describe the algorithms, and the algorithmic engineering necessary to find structures that subscribe to this notion, the challenges in handling such a huge data set, and the results of our experiment. Keywords: web mining, communities, trawling, link analysis

 

Gopal Pandurangan, Prabhakar Raghavany, Eli Upfal

http://www.cs.brown.edu/people/eli/

Pandurangan G., Raghavany P., Upfal E., [2001], "Building Low-Diameter P2P Networks", 42nd Annual Symposium on Foundations of Computer Science (FOCS01), pp. 492-499

Abstract : In a peer-to-peer (P2P) network, nodes connect into an existing network and participate in providing and availing of services. There is no dichotomy between a central server and distributed clients. Current P2P networks (e.g., Gnutella) are constructed by participants following their own un-coordinated (and often whimsical) protocols; they consequently suffer from frequent network overload and fragmentation into disconnected pieces separated by chokepoints with inadequate bandwidth. In this paper we propose a simple scheme for participants to build P2P networks in a distributed fashion, and prove that it results in connected networks of constant degree and logarithmic diameter. It does so with no global knowledge of all the nodes in the network. In the most common P2P application to date (search), these properties are crucial.

 

Chen Q., Chang H., Govindan R., Jamin S., Shenker S.J., Willinger W. [2002], "The Origin of Power Laws in Internet Topologies Revisited", Proc. of IEEE Infocom 2002.

Abstract : In a recent paper, Faloutsos et al. [1] found that the inter Autonomous System (AS) topology exhibits a power-law vertex degree distribution. This result was quite unexpected in the networking community and stirred significant interest in exploring the possible causes of this phenomenon. The work of Barabasi and Albert [2] and its application to network topology generation in the work of Medina et al. [3] have explored a promising class of models that yield strict power-law vertex degree distributions. In this paper, we re-examine the BGP measurements that form the basis for the results reported in [1]. We find that by their very nature (i.e., being strictly BGP-based), the data provides a very incomplete picture of Internet connectivity at the AS level. The AS connectivity maps constructed from this data (the original maps) typically miss 20–50% or even more of the physical links in AS maps constructed using additional sources (the extended maps). Subsequently, we find that while the vertex degree distributions resulting from the extended maps are heavy-tailed, they deviate significantly from a strict power law. Finally, we show that available historical data does not support the connectivity-based dynamics assumed in [2]. Together, our results suggest that the Internet topology at the AS level may well have developed over time following a very different set of growth processes than those proposed in [2].

 

Tangmunarunkit H., Govindan R., Jamin S., Shenker S., Willinger W. [2001], "Network Topologies, Power Laws, and Hierarchy", Tech Report USC-CS-01-746.

Abstract : It has long been thought that the Internet, and its constituent networks, are hierarchical in nature. Consequently, the network topology generators most widely used by the Internet research community, GT-ITM [7] and Tiers [11], create networks with a deliberately hierarchical structure. However, recent work by Faloutsos et al. [13] revealed that the Internet’s degree distribution— the distribution of the number of connections routers or Autonomous Systems (ASs) have — is a power-law. The degree distributions produced by the GT-ITM and Tiers generators are not power-laws. To rectify this problem, several new network generators have recently been proposed that produce more realistic degree distributions; these new generators do not attempt to create a hierarchical structure but instead focus solely on the degree distribution. There are thus two families of network generators, structural generators that treat hierarchy as fundamental and degree-based generators that treat the degree distribution as fundamental. In this paper we use several topology metrics to compare the networks produced by these two families of generators to current measurements of the Internet graph. We find that the degree-based generators produce better models, at least according to our topology metrics, of both the AS-level and router-level Internet graphs. We then seek to resolve the seeming paradox that while the Internet certainly has hierarchy, it appears that the Internet graphs are better modeled by generators that do not explicitly construct hierarchies. We conclude our paper with a brief study of other network structures, such as the pointer structure in the web and the set of airline routes, some of which turn out to have metric properties similar to that of the Internet.

 

Newman M.E.J., Watts D.J., Strogatz S.H. [2001], "Random graph models of social networks", Working Paper, Santa Fe Institute.

We describe some new exactly solvable models of the structure of social networks, based on random graphs with arbitrary degree distributions. We give models both for simple unipartite networks, such as acquaintance networks, and bipartite networks, such as affiliation networks. We compare the predictions of our models to data for a number of real-world social networks and find that in some cases the models are in remarkable agreement with the data, while in others the agreement is poorer, perhaps indicating the presence of additional social structure in the network that is not captured by the random graph.

 

Newman M.E.J. [2002], "Random Graphs as Models of Networks", Working Paper, Santa Fe Institute.

http://www.santafe.edu/sfi/publications/wpabstract/200202005

Abstract: The random graph of Erdos and Renyi is one of the oldest and best studied models of a network, and possesses the considerable advantage of being exactly solvable for many of its average properties. However, as a model of real-world networks such as the Internet, social networks or biological networks it leaves a lot to be desired. In particular, it differs from real networks in two crucial ways: it lacks network clustering or transitivity, and it has an unrealistic Poissonian degree distribution. In this paper we review some recent work on generalizations of the random graph aimed at correcting these shortcomings. We describe generalized random graph models of both directed and undirected networks that incorporate arbitrary non-Poisson degree distributions, and extensions of these models that incorporate clustering too. We also describe two recent applications of random graph models to the problems of network robustness and of epidemics spreading on contact networks. Keywords: networks, random graphs, social networks, small world

 

Tony H. Grubesic, Department of Geography, The Ohio State University, Columbus, OH 43210-1361, USA

Grubesic T. H. [2002], "Spatial dimensions of Internet activity", Telecommunications Policy, Volume 26, Issues 7-8, August-September 2002.

Abstract : The global diffusion of Internet activity is advancing at an unprecedented rate. However, it is increasingly apparent that the diffusion of information technologies and their associated activity is spatially uneven. Utilizing a comprehensive database of domain registrations, spatial¯statistical methods, and a geographic information system (GIS), the spatial dimensions of Internet activity are explored for the state of Ohio. In addition to identifying considerable differences in Internet activity between urban and rural locales, results suggest that existing telecommunication infrastructure and educational institutions also play significant roles in the level of Internet-related activity for the region. Author Keywords: Internet activity; Domains; Spatial analysis; GIS; Ohio

 

Sean P. Gormana and Edward J. Malecki, School of Public Policy, George Mason University, Finley Building, 4400 University Drive, Fairfax, VA 22030, USA and Department of Geography and Center for Urban and Regional Analysis, Ohio State University, 1036 Derby Hall, 154 North Oval Mall, Columbus, OH 43210-1361, USA

Gormana S. P., Malecki E. J. [2002],"Fixed and fluid: stability and change in the geography of the Internet", Telecommunications Policy, Volume 26, Issues 7-8, August-September 2002.

Abstract : The geography of today's Internet infrastructure is grounded in the fiber installations, routers, switches and central offices that guide electronic messages around the world. While the location of hardware is relatively fixed, the task of identifying the locations where data and information are stored is a far more difficult task. Advances in technology have created a very fluid definition of the location of information that has become increasingly distributed and ethereal. This paper examines the current structure and location patterns of Internet infrastructure hardware in the USA and how content distribution networks and peer-to-peer networks have disrupted traditional information location. The comparison of the two provides insight into how the geography of infrastructure hardware is influencing Internet technology and business. Author Keywords: Internet; Infrastructure; Peer-to-peer; Cybergeography

 

Quah D. [2000], "Internet cluster emergence", European Economic Review, vol. 44, pp. 1032–1044.

Quah D. [2001], "Technology Dissemination and the Economic Growth: Some Lessons for the New Economy", LSE Economics Department, April 2001.

Wimmer B. S., Townsend A., Chezum B.E. [2000], "Information Technologies and the Middleman: The Changing Role of Information Intermediaries in an Information–Rich Economy", Journal of Labor Research, vol. XXI, n°3, Summer, pp. 407–418.

---

 

Venkatesh Bala, Sanjeev Goyal

Bala V., S. Goyal [2000], "A Strategic Analysis of Network Reliability", Review of Economic Design Vol 5- 3 (http://www.few.eur.nl/few/people/goyal/).

We consider a non-cooperative model of information networks where communication is costly and not fully reliable. We examine the nature of Nash networks and efficient networks. We find that if the society is large, and link formation costs are moderate, Nash networks as well as efficient networks will be `super-connected', i.e. every link is redundant in the sense that the network remains connected even after the link is deleted. This contrasts with the properties of a deterministic model of information decay, where Nash networks typically involve unique paths between agents. We also find that if costs are very low or very high, or if links are highly reliable then there is virtually no conflict between efficiency and stability. However, for intermediate values of costs and link reliability, Nash networks may be underconnected relative to the social optimum.

Bala V., Goyal S. [2001], "Conformism and Diversity under Social Learning", Economic Theory, Vol.17, Iss.1, p. 101-120

http://www.few.eur.nl/few/people/goyal/.

When there are competing technologies or products with unknown payoffs an important question is which technology will prevail and whether technologies with different payoffs can coexist in the long run. In this paper, we use a social learning model with local interactions to study this question. We show that the adoption of technologies as well as the prospects of conformism/diversity depend crucially on the nature of information flows and the heterogeneity of individual preferences in a society. In a society with homogeneous individuals, a superior technology drives out an inferior technology; however, two technologies with the same payoffs can coexist under certain interaction patterns. We also examine a society with individuals who have heterogeneous preferences. In this setting, we illustrate how heterogeneity of individual preferences can combine with local interaction to create information barriers that lead technologies with different payoffs to coexist, in the long run.

 

Sergio Currarini, Massimo Morelli

Currarini S., Morelli M. [2000], "Network formation with sequential demands", Review of Economic Design, Vol 5- 3

http://econpapers.hhs.se/article/sprreecde/

 

Matthew O. Jackson

Jackson M.O. [2001], "The Stability and Efficiency of Economic and Social Networks", Working Paper

This paper studies the formation of networks among individuals. The focus is on the compatibility of overall societal welfare with individual incentives to form and sever links. The paper reviews and synthesizes some previous results on the subject, and also provides new results on the existence of pairwise-stable networks and the relationship between pairwise stable and efficient networks in a variety of contexts and under several definitions of efficiency.