Hierarchical structure and the prediction of missing links in networks (2008)
Clauset, Aaron, Moore, Cristopher, Newman, M. E. J.
Networks have in recent years emerged as an invaluable tool for describing and quantifying complex systems in many branches of science. Recent studies suggest that networks often exhibit hierarchical...
The first-mover advantage in scientific publication (2008)
Mathematical models of the scientific citation process predict a strong "first-mover" effect under which the first papers in a field will, essentially regardless of content, receive citations at a...
Community structure in directed networks (2007)
Leicht, E. A., Newman, M. E. J.
We consider the problem of finding communities or modules in directed networks. The most common approach to this problem in the previous literature has been simply to ignore edge direction and apply...
Robustness of community structure in networks (2007)
Karrer, Brian, Levina, Elizaveta, Newman, M. E. J.
The discovery of community structure is a common challenge in the analysis of network data. Many methods have been proposed for finding community structure, but few have been proposed for determining...
Bicomponents and the robustness of networks to failure (2007)
Newman, M. E. J., Ghoshal, Gourab
A common definition of a robust connection between two nodes in a network such as a communication network is that there should be at least two independent paths connecting them, so that the failure...
Component sizes in networks with arbitrary degree distributions (2007)
We give an exact solution for the complete distribution of component sizes in random networks with arbitrary degree distributions. The solution tells us the probability that a randomly chosen node...
Power-law distributions in empirical data (2007)
Clauset, Aaron, Shalizi, Cosma Rohilla, Newman, M. E. J.
Power-law distributions occur in many situations of scientific interest and have significant consequences for our understanding of natural and man-made phenomena. Unfortunately, the empirical...
Large-scale structure of time evolving citation networks (2007)
Leicht, E. A., Clarkson, Gavin, Shedden, Kerby, Newman, M. E. J.
In this paper we examine a number of methods for probing and understanding the large-scale structure of networks that evolve over time. We focus in particular on citation networks, networks of...
Community structure in the U.S. House of Representatives (2006)
Porter, Mason A., Friend, A. J., Mucha, Peter J., Newman, M. E. J.
Studies like these indicate that network theory can be of substantial use in uncovering collaborative structure in political bodies such as the U.S. Congress, without requiring input in the form of...
Mixture models and exploratory analysis in networks (2006)
Newman, M. E. J., Leicht, E. A.
Networks are widely used in the biological, physical, and social sciences as a concise mathematical representation of the topology of systems of interacting components. Understanding the structure of...
Structural Inference of Hierarchies in Networks (2006)
Clauset, Aaron, Moore, Cristopher, Newman, M. E. J.
One property of networks that has received comparatively little attention is hierarchy, i.e., the property of having vertices that cluster together in groups, which then join to form groups of...
Growing distributed networks with arbitrary degree distributions (2006)
Ghoshal, Gourab, Newman, M. E. J.
We consider distributed networks, such as peer-to-peer networks, whose structure can be manipulated by adjusting the rules by which vertices enter and leave the network. We focus in particular on...
Finding community structure in networks using the eigenvectors of matrices (2006)
We consider the problem of detecting communities or modules in networks, groups of vertices with a higher-than-average density of edges connecting them. Previous work indicates that a robust approach...
Exact solutions for models of evolving networks with addition and deletion of nodes (2006)
Moore, Cristopher, Ghoshal, Gourab, Newman, M. E. J.
There has been considerable recent interest in the properties of networks, such as citation networks and the worldwide web, that grow by the addition of vertices, and a number of simple solvable...
Optimal design of spatial distribution networks (2006)
Gastner, Michael T., Newman, M. E. J.
We consider the problem of constructing public facilities, such as hospitals, airports, or malls, in a country with a non-uniform population density, such that the average distance from a person's...
Nonequilibrium phase transition in the coevolution of networks and opinions (2006)
Holme, Petter, Newman, M. E. J.
Models of the convergence of opinion in social systems have been the subject of a considerable amount of recent attention in the physics literature. These models divide into two classes, those in...
Modularity and community structure in networks (2006)
Many networks of interest in the sciences, including a variety of social and biological networks, are found to divide naturally into communities or modules. The problem of detecting and...
Community Structure in the United States House of Representatives (2006)
Porter, Mason A., Mucha, Peter J., Newman, M. E. J., Friend, A. J.
We investigate the networks of committee and subcommittee assignments in the United States House of Representatives from the 101st--108th Congresses, with the committees connected by ``interlocks''...
Shape and efficiency in spatial distribution networks (2006)
Gastner, Michael T, Newman, M. E. J.
We study spatial networks that are designed to distribute or collect a commodity, such as gas pipelines or train tracks. We focus on the cost of a network, as represented by the total length of all...
The spatial structure of networks (2006)
Gastner, Michael T, Newman, M. E.J.
We study networks that connect points in geographic space, such astransportation networks and the Internet. We find that there are strongsignatures in these networks of topography and use patterns,...
Vertex similarity in networks (2005)
Leicht, E. A., Holme, Petter, Newman, M. E. J.
We consider methods for quantifying the similarity of vertices in networks. We propose a measure of similarity based on the concept that two vertices are similar if their immediate neighbors in the...
A network-based ranking system for US college football (2005)
Park, Juyong, Newman, M. E. J.
American college football faces a conflict created by the desire to stage national championship games between the best teams of a season when there is no conventional play-off system for deciding...
A network-based ranking system for American college football (2005)
Park, Juyong, Newman, M. E. J.
American college football faces a conflict created by the desire to stage national championship games between the best teams of a season when there is no conventional playoff system to decide which...
A network analysis of committees in the United States House of Representatives (2005)
Porter, Mason A., Mucha, Peter J., Newman, M. E. J., Warmbrand, Casey M.
Network theory provides a powerful tool for the representation and analysis of complex systems of interacting agents. Here we investigate the United States House of Representatives network of...
Threshold effects for two pathogens spreading on a network (2005)
Diseases spread through host populations over the networks of contacts between individuals, and a number of results about this process have been derived in recent years by exploiting connections...
Solution for the properties of a clustered network (2004)
Park, Juyong, Newman, M. E. J.
We study Strauss's model of a network with clustering and present an analytic mean-field solution which is exact in the limit of large network size. Previous computer simulations have revealed a...
Power laws, Pareto distributions and Zipf's law (2004)
When the probability of measuring a particular value of some quantity varies inversely as a power of that value, the quantity is said to follow a power law, also known variously as Zipf's law or the...
Shape and efficiency in spatial distribution networks (2004)
Gastner, Michael T., Newman, M. E. J.
We study spatial networks that are designed to distribute or collect a commodity, such as gas pipelines or train tracks. We focus on the cost of a network, as represented by the total length of all...
Finding community structure in very large networks (2004)
Clauset, Aaron, Newman, M. E. J., Moore, Cristopher
The discovery and analysis of community structure in networks is a topic of considerable recent interest within the physics community, but most methods proposed so far are unsuitable for very large...
The spatial structure of networks (2004)
Gastner, Michael T., Newman, M. E. J.
We study networks that connect points in geographic space, such as transportation networks and the Internet. We find that there are strong signatures in these networks of topography and use patterns,...
Analysis of weighted networks (2004)
The connections in many networks are not merely binary entities, either present or not, but have associated weights that record their strengths relative to one another. Recent studies of networks...
Technological networks and the spread of computer viruses (2004)
Balthrop, Justin, Forrest, Stephanie, Newman, M. E. J., Williamson, Matthew M.
Computer infections such as viruses and worms spread over networks of contacts between computers, with different types of networks being exploited by different types of infections. Here we analyze...
The statistical mechanics of networks (2004)
Park, Juyong, Newman, M. E. J.
We study the family of network models derived by requiring the expected properties of a graph ensemble to match a given set of measurements of a real-world network, while maximizing the entropy of...
Solution of the 2-star model of a network (2004)
Park, Juyong, Newman, M. E. J.
The p-star model or exponential random graph is among the oldest and best-known of network models. Here we give an analytic solution for the particular case of the 2-star model, which is one of the...
Identifying the role that individual animals play in their social network (2004)
Lusseau, David, Newman, M. E. J.
Techniques recently developed for the analysis of human social networks are applied to the social network of bottlenose dolphins living in Doubtful Sound, New Zealand. We identify communities and...
Detecting community structure in networks (2004)
There has been considerable recent interest in algorithms for finding communities in networks--groups of vertices within which connections are dense, but between which connections are sparser. Here...
Diffusion-based method for producing density equalizing maps (2004)
Gastner, Michael T., Newman, M. E. J.
Map makers have long searched for a way to construct cartograms -- maps in which the sizes of geographic regions such as countries or provinces appear in proportion to their population or some other...
On the uniform generation of random graphs with prescribed degree sequences (2003)
Milo, R., Kashtan, N., Itzkovitz, S., Newman, M. E. J., Alon, U.
Random graphs with prescribed degree sequences have been widely used as a model of complex networks. Comparing an observed network to an ensemble of such graphs allows one to detect deviations from...
Fast algorithm for detecting community structure in networks (2003)
It has been found that many networks display community structure -- groups of vertices within which connections are dense but between which they are sparser -- and highly sensitive computer...
A measure of betweenness centrality based on random walks (2003)
Betweenness is a measure of the centrality of a node in a network, and is normally calculated as the fraction of shortest paths between node pairs that pass through the node of interest. Betweenness...
Finding and evaluating community structure in networks (2003)
We propose and study a set of algorithms for discovering community structure in networks -- natural divisions of network nodes into densely connected subgroups. Our algorithms all share two...
Why social networks are different from other types of networks (2003)
Newman, M. E. J., Park, Juyong
We argue that social networks differ from most other types of networks, including technological and biological networks, in two important ways. First, they have non-trivial clustering or network...
The structure and function of complex networks (2003)
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...
The origin of degree correlations in the Internet and other networks (2003)
Park, Juyong, Newman, M. E. J.
It has been argued that the observed anticorrelation between the degrees of adjacent vertices in the network representation of the Internet has its origin in the restriction that no two vertices have...
Properties of highly clustered networks (2003)
We propose and solve exactly a model of a network that has both a tunable degree distribution and a tunable clustering coefficient. Among other things, our results indicate that increased clustering...
Mixing patterns and community structure in networks (2002)
Common experience suggests that many networks might possess community structure - division of vertices into groups, with a higher density of edges within groups than between them. Here we describe a...
Mixing patterns in networks (2002)
We study assortative mixing in networks, the tendency for vertices in networks to be connected to other vertices that are like (or unlike) them in some way. We consider mixing according to discrete...
Assortative mixing in networks (2002)
A network is said to show assortative mixing if the nodes in the network that have many connections tend to be connected to other nodes with many connections. We define a measure of assortative...
Identity and Search in Social Networks (2002)
Watts, D. J., Dodds, P. S., Newman, M. E. J.
Social networks have the surprising property of being "searchable": Ordinary people are capable of directing messages through their network of acquaintances to reach a specific but distant target...
The spread of epidemic disease on networks (2002)
The study of social networks, and in particular the spread of disease on networks, has attracted considerable recent attention in the physics community. In this paper, we show that a large class of...
Convergence of threshold estimates for two-dimensional percolation (2002)
Using a recently introduced algorithm for simulating percolation in microcanonical (fixed-occupancy) samples, we study the convergence with increasing system size of a number of estimates for the...
Optimal design, robustness, and risk aversion (2002)
Newman, M. E. J., Girvan, Michelle, Farmer, J. Doyne
Highly optimized tolerance is a model of optimization in engineered systems, which gives rise to power-law distributions of failure events in such systems. The archetypal example is the highly...
Random graphs as models of networks (2002)
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....
Exact solutions of epidemic models on networks (2002)
The study of social networks, and in particular the spread of disease on networks, has attracted considerable recent attention in the physics community. In this paper, we show that a large class of...
Community structure in social and biological networks (2001)
Girvan, Michelle, Newman, M. E. J.
A number of recent studies have focused on the statistical properties of networked systems such as social networks and the World-Wide Web. Researchers have concentrated particularly on a few...
Ego-centered networks and the ripple effect (2001)
Recent work has demonstrated that many social networks, and indeed many networks of other types also, have broad distributions of vertex degree. Here we show that this has a substantial impact on the...
Percolation and epidemics in a two-dimensional small world (2001)
Newman, M. E. J., Jensen, I., Ziff, R. M.
Percolation on two-dimensional small-world networks has been proposed as a model for the spread of plant diseases. In this paper we give an analytic solution of this model using a combination of...
Dynamics of a simple evolutionary process (2001)
Stauffer, Dietrich, Newman, M. E. J.
We study the simple evolutionary process in which we repeatedly find the least fit agent in a population of agents and give it a new fitness which is chosen independently at random from a specified...
A Simple Model of Epidemics with Pathogen Mutation (2001)
Girvan, Michelle, Callaway, Duncan S., Newman, M. E. J., Strogatz, Steven H.
We study how the interplay between the memory immune response and pathogen mutation affects epidemic dynamics in two related models. The first explicitly models pathogen mutation and individual...
Are randomly grown graphs really random? (2001)
Callaway, Duncan S., Hopcroft, John E., Kleinberg, Jon M., Newman, M. E. J., Strogatz, Steven H.
We analyze a minimal model of a growing network. At each time step, a new vertex is added; then, with probability delta, two vertices are chosen uniformly at random and joined by an undirected edge....
Clustering and preferential attachment in growing networks (2001)
We study empirically the time evolution of scientific collaboration networks in physics and biology. In these networks, two scientists are considered connected if they have coauthored one or more...
A fast Monte Carlo algorithm for site or bond percolation (2001)
We describe in detail a new and highly efficient algorithm for studying site or bond percolation on any lattice. The algorithm can measure an observable quantity in a percolation system for all...
Who is the best connected scientist? A study of scientific coauthorship networks (2000)
Using data from computer databases of scientific papers in physics, biomedical research, and computer science, we have constructed networks of collaboration between scientists in each of these...
Glassiness and constrained dynamics of a short-range non-disordered spin model (2000)
Garrahan, Juan P., Newman, M. E. J.
We study the low temperature dynamics of a two dimensional short-range spin system with uniform ferromagnetic interactions, which displays glassiness at low temperatures despite the absence of...
Network robustness and fragility: Percolation on random graphs (2000)
Callaway, D. S., Newman, M. E. J., Strogatz, S. H., Watts, D. J.
Recent work on the internet, social networks, and the power grid has addressed the resilience of these networks to either random or targeted deletion of network nodes. Such deletions include, for...
Random graphs with arbitrary degree distributions and their applications (2000)
Newman, M. E. J., Strogatz, S. H., Watts, D. J.
Recent work on the structure of social networks and the internet has focussed attention on graphs with distributions of vertex degree that are significantly different from the Poisson degree...
The structure of scientific collaboration networks (2000)
We investigate the structure of scientific collaboration networks. We consider two scientists to be connected if they have authored a paper together, and construct explicit networks of such...
Efficient Monte Carlo algorithm and high-precision results for percolation (2000)
We present a new Monte Carlo algorithm for studying site or bond percolation on any lattice. The algorithm allows us to calculate quantities such as the cluster size distribution or spanning...
Exact solution of site and bond percolation on small-world networks (2000)
Moore, Cristopher, Newman, M. E. J.
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...
Models of the Small World: A Review (2000)
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...
Epidemics and percolation in small-world networks (1999)
Moore, Cristopher, Newman, M. E. J.
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...
Simple models of evolution and extinction (1999)
This article gives a brief introduction to the mathematical modeling of large-scale biological evolution and extinction. We give three examples of simple models in this field: the coevolutionary...
Mean-field solution of the small-world network model (1999)
Newman, M. E. J., Moore, C., Watts, D. J.
The small-world network model is a simple model of the structure of social networks, which simultaneously possesses characteristics of both regular lattices and random graphs. The model consists of a...
Models of Extinction: A Review (1999)
Newman, M. E. J., Palmer, R. G.
We review recent work aimed at modeling species extinction over geological time. We discuss a number of models which, rather than dealing with the direct causes of particular extinction events,...
The physical limits of communication (1999)
Lachmann, Michael, Newman, M. E. J., Moore, Cristopher
It has been well-known since the pioneering work of Claude Shannon in the 1940s that a message transmitted with optimal efficiency over a channel of limited bandwidth is indistinguishable from random...
Scaling and percolation in the small-world network model (1999)
Newman, M. E. J., Watts, D. J.
In this paper we study the small-world network model of Watts and Strogatz, which mimics some aspects of the structure of networks of social interactions. We argue that there is one non-trivial...
Renormalization group analysis of the small-world network model (1999)
Newman, M. E. J., Watts, D. J.
We study the small-world network model, which mimics the transition between regular-lattice and random-lattice behavior in social networks of increasing size. We contend that the model displays a...
Moore, Cristopher, Newman, M. E. J.
We study the four-state antiferromagnetic Potts model on the triangular lattice. We show that the model has six types of defects which diffuse and annihilate according to certain conservation laws...
Power spectra of extinction in the fossil record (1998)
Newman, M. E. J., Eble, Gunther J.
Recent Fourier analyses of fossil extinction data have indicated that the power spectrum of extinction during the Phanerozoic may take the form of 1/f noise, a result which, it has been suggested,...
Extinction, diversity and survivorship of taxa in the fossil record (1998)
Newman, M. E. J., Sibani, Paolo
Using data drawn from large-scale databases, a number of interesting trends in the fossil record have been observed in recent years. These include the average decline in extinction rates throughout...
Decline in extinction rates and scale invariance in the fossil record (1998)
Newman, M. E. J., Eble, Gunther J.
We show that the decline in the extinction rate during the Phanerozoic can be accurately parameterized by a logarithmic fit to the cumulative total extinction. This implies that extinction intensity...
Error estimation in the histogram Monte Carlo method (1998)
Newman, M. E. J., Palmer, R. G.
We examine the sources of error in the histogram reweighting method for Monte Carlo data analysis. We demonstrate that, in addition to the standard statistical error which has been studied elsewhere,...
Effects of neutral selection on the evolution of molecular species (1997)
Newman, M. E. J., Engelhardt, Robin
We introduce a new model of evolution on a fitness landscape possessing a tunable degree of neutrality. The model allows us to study the general properties of molecular species undergoing neutral...
Glassy dynamics and aging in an exactly solvable spin model (1997)
Newman, M. E. J., Moore, Cristopher
We introduce a simple two-dimensional spin model with short-range interactions which shows glassy behavior despite a Hamiltonian which is completely homogeneous and possesses no randomness. We solve...
Monte Carlo simulation of ice models (1997)
Barkema, G. T., Newman, M. E. J.
We propose a number of Monte Carlo algorithms for the simulation of ice models and compare their efficiency. One of them, a cluster algorithm for the equivalent three colour model, appears to have a...
New Monte Carlo algorithms for classical spin systems (1997)
Barkema, G. T., Newman, M. E. J.
We describe a number of recently developed cluster-flipping algorithms for the efficient simulation of classical spin models near their critical temperature. These include the algorithms of Wolff,...
Diffusion constant for the repton model of gel electrophoresis (1997)
Newman, M. E. J., Barkema, G. T.
The repton model is a simple model of the "reptation" motion by which DNA diffuses through a gel during electrophoresis. In this paper we show that the model can be mapped onto a system consisting of...
A model of mass extinction (1997)
A number of authors have in recent years proposed that the processes of macroevolution may give rise to self-organized critical phenomena which could have a significant effect on the dynamics of...