M E J Newman
Biographic Data
| ID | 7581 |
|---|---|
| NAME | M E J Newman |
| GIVEN NAMES | M E J |
| FAMILY NAME | Newman |
| SIGNATURE | NEWMAN M E J |
| AFFILIATIONS | Santa Fe Institute |
| ORCID | 0000-0002-0907-1660 |
| VERIFIED | Yes |
| TOTAL WORKS | 36 |
| TOTAL CITATIONS | 124 |
| AUTHOR COUNT | 36 |
| EDITOR COUNT | 0 |
| FIRST PUBLICATION YEAR | 2000 |
| LATEST PUBLICATION YEAR | 2019 |
| H-INDEX | 3 |
Structure of Online Dating Markets in U.S. Cities
We study the structure of heterosexual dating markets in the United States through an analysis of the interactions of several million users of a large online dating website, applying recently developed network analysis methods to the pattern of messages exchanged among users. Our analysis shows that the strongest driver of romantic interaction at the national level is simple geographic proximity, but at the local level, other demographic factors …
Friendship networks and social status
In empirical studies of friendship networks, participants are typically asked, in interviews or questionnaires, to identify some or all of their close friends, resulting in a directed network in which friendships can, and often do, run in only one direction between a pair of individuals. Here we analyze a large collection of such networks representing friendships among students at US high and junior-high schools and show that the pattern of unrec…
Network Robustness and Fragility: Percolation on Random Graphs
Stochastic blockmodels and community structure in networks
Stochastic blockmodels have been proposed as a tool for detecting community structure in networks as well as for generating synthetic networks for use as benchmarks. Most blockmodels, however, ignore variation in vertex degree, making them unsuitable for applications to real-world networks, which typically display broad degree distributions that can significantly affect the results. Here we demonstrate how the generalization of blockmodels to inc…
The Structure and Dynamics of Networks
From the Internet to networks of friendship, disease transmission, and even terrorism, the concept--and the reality--of networks has come to pervade modern society. But what exactly is a network? What different types of networks are there? Why are they interesting, and what can they tell us? In recent years, scientists from a range of fields--including mathematics, physics, computer science, sociology, and biology--have been pursuing these questi…
Networks
Fundamental network algorithms
The large-scale structure of networks
Measures and metrics
If we know the structure of a network we can calculate from it a variety of useful quantities or measures that capture particular features of the network topology. This chapter looks at some of these measures, including degree centrality, eigenvector centrality, Katz centrality, transitivity, reciprocity, and similarity. Exercises are provided at the end of the chapter.
Epidemics on networks
One of the reasons for the large investment the scientific community has made in the study of social networks is their connection with the spread of disease. Diseases spread over networks of contacts between individuals: airborne diseases like influenza or tuberculosis are communicated when two people breathe the air in the same room; contagious diseases and parasites can be communicated when people touch; HIV and other sexually transmitted disea…
Power-Law Distributions in Empirical Data
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 detection and characterization of power laws is complicated by the large fluctuations that occur in the tail of the distribution -- the part of the distribution representing large but rare events -- and by the difficulty of identifying the range over which power-law b…
Finding community structure in networks using the eigenvectors of matrices
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 to this problem is the maximization of the benefit function known as "modularity" over possible divisions of a network. Here we show that this maximization process can be written in terms of the eigenspectrum of a matrix we call the modularity matrix…
Modularity and community structure in networks
Many networks of interest in the sciences, including social networks, computer networks, and metabolic and regulatory networks, are found to divide naturally into communities or modules. The problem of detecting and characterizing this community structure is one of the outstanding issues in the study of networked systems. One highly effective approach is the optimization of the quality function known as “modularity” over the possible divisions of…
A measure of betweenness centrality based on random walks
Fast algorithm for detecting community structure in networks
Many networks display community structure--groups of vertices within which connections are dense but between which they are sparser--and sensitive computer algorithms have in recent years been developed for detecting this structure. These algorithms, however, are computationally demanding, which limits their application to small networks. Here we describe an algorithm which gives excellent results when tested on both computer-generated and real-w…
Detecting community structure in networks
Diffusion-based method for producing density-equalizing maps
Map makers have for many years 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 analogous property. Such maps are invaluable for the representation of census results, election returns, disease incidence, and many other kinds of human data. Unfortunately, to scale regions and still have them fit together, one is normally f…
Finding and evaluating community structure in networks
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 definitive features: first, they involve iterative removal of edges from the network to split it into communities, the edges removed being identified using any one of a number of possible "betweenness" measures, and second, these measures are, crucially, recalcul…
Analysis of weighted networks
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 have, by and large, steered clear of such weighted networks, which are often perceived as being harder to analyze than their unweighted counterparts. Here we point out that weighted networks can in many cases be analyzed using a simple mapping from a wei…
Coauthorship networks and patterns of scientific collaboration
By using data from three bibliographic databases in biology, physics, and mathematics, respectively, networks are constructed in which the nodes are scientists, and two scientists are connected if they have coauthored a paper. We use these networks to answer a broad variety of questions about collaboration patterns, such as the numbers of papers authors write, how many people they write them with, what the typical distance between scientists is t…
Finding community structure in very large networks
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 networks because of their computational cost. Here we present a hierarchical agglomeration algorithm for detecting community structure which is faster than many competing algorithms: its running time on a network with n vertices and m edges is O (md lo…
Mixing patterns in networks
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 characteristics such as language or race in social networks and scalar characteristics such as age. As a special example of the latter we consider mixing according to vertex degree, i.e., according to the number of connections vertices have to other ve…
Why social networks are different from other types of networks
We argue that social networks differ from most other types of networks, including technological and biological networks, in two important ways. First, they have nontrivial clustering or network transitivity and second, they show positive correlations, also called assortative mixing, between the degrees of adjacent vertices. Social networks are often divided into groups or communities, and it has recently been suggested that this division could ac…
The Structure and Function of Complex Networks
Inspired by empirical studies of networked systems such as the Internet, social networks, and bio-logical 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 eect, degree distributions, clustering, network correlations, random graph models, models of network growt…
Modeling Extinction
Developed after a meeting at the Santa Fe Institute on extinction modeling, this book comments critically on the various modeling approaches. In the last decade or so, scientists have started to examine a new approach to the patterns of evolution and extinction in the fossil record. This approach may be called "statistical paleontology," since it looks at large-scale patterns in the record and attempts to understand and model their average statis…
The Structure and Dynamics of Networks
From the Internet to networks of friendship, disease transmission, and even terrorism, the concept--and the reality--of networks has come to pervade modern society. But what exactly is a network? What different types of networks are there? Why are they interesting, and what can they tell us? In recent years, scientists from a range of fields--including mathematics, physics, computer science, sociology, and biology--have been pursuing these questi…
Friendship networks and social status
In empirical studies of friendship networks, participants are typically asked, in interviews or questionnaires, to identify some or all of their close friends, resulting in a directed network in which friendships can, and often do, run in only one direction between a pair of individuals. Here we analyze a large collection of such networks representing friendships among students at US high and junior-high schools and show that the pattern of unrec…
Structure of Online Dating Markets in U.S. Cities
We study the structure of heterosexual dating markets in the United States through an analysis of the interactions of several million users of a large online dating website, applying recently developed network analysis methods to the pattern of messages exchanged among users. Our analysis shows that the strongest driver of romantic interaction at the national level is simple geographic proximity, but at the local level, other demographic factors …
Network Robustness and Fragility: Percolation on Random Graphs
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 or links. Such deletions include, for example, the failure of Internet routers or power transmission lines. Percolation models on random graphs provide a simple representation of this process but have typically been limited to graphs with Poisson degree distribution at their vertice…
Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality
Using computer databases of scientific papers in physics, biomedical research, and computer science, we have constructed networks of collaboration between scientists in each of these disciplines. In these networks two scientists are considered connected if they have coauthored one or more papers together. Here we study a variety of nonlocal statistics for these networks, such as typical distances between scientists through the network, and measur…
Scientific collaboration networks. I. Network construction and fundamental results
Using computer databases of scientific papers in physics, biomedical research, and computer science, we have constructed networks of collaboration between scientists in each of these disciplines. In these networks two scientists are considered connected if they have coauthored one or more papers together. We study a variety of statistical properties of our networks, including numbers of papers written by authors, numbers of authors per paper, num…
Clustering and preferential attachment in growing networks
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 papers together. We show that the probability of a pair of scientists collaborating increases with the number of other collaborators they have in common, and that the probability of a particular scientist acquiring new collaborators increases with the nu…
Random graphs with arbitrary degree distributions and their applications
Recent work on the structure of social networks and the internet has focused attention on graphs with distributions of vertex degree that are significantly different from the Poisson degree distributions that have been widely studied in the past. In this paper we develop in detail the theory of random graphs with arbitrary degree distributions. In addition to simple undirected, unipartite graphs, we examine the properties of directed and bipartit…
The structure of scientific collaboration networks
The structure of scientific collaboration networks is investigated. Two scientists are considered connected if they have authored a paper together and explicit networks of such connections are constructed by using data drawn from a number of databases, including MEDLINE (biomedical research), the Los Alamos e-Print Archive (physics), and NCSTRL (computer science). I show that these collaboration networks form “small worlds,” in which randomly cho…
Assortative Mixing in Networks
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. Here we measure mixing patterns in a variety of networks and find that social networks are mostly assortatively mixed, but that technological and biological networks tend to be disassortative. We propose a model of an assortatively mixed network, which we study both analytically and numeric…
Spread of epidemic disease on networks
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 standard epidemiological models, the so-called susceptible/infective/removed (SIR) models can be solved exactly on a wide variety of networks. In addition to the standard but unrealistic case of fixed infectiveness time and fixed and uncorrelated proba…
Random graph models of social networks
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 da…
Community structure in social and biological networks
A number of recent studies have focused on the statistical properties of networked systems such as social networks and the Worldwide Web. Researchers have concentrated particularly on a few properties that seem to be common to many networks: the small-world property, power-law degree distributions, and network transitivity. In this article, we highlight another property that is found in many networks, the property of community structure, in which…
Mixing patterns in networks
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 characteristics such as language or race in social networks and scalar characteristics such as age. As a special example of the latter we consider mixing according to vertex degree, i.e., according to the number of connections vertices have to other ve…
Why social networks are different from other types of networks
We argue that social networks differ from most other types of networks, including technological and biological networks, in two important ways. First, they have nontrivial clustering or network transitivity and second, they show positive correlations, also called assortative mixing, between the degrees of adjacent vertices. Social networks are often divided into groups or communities, and it has recently been suggested that this division could ac…
The Structure and Function of Complex Networks
Inspired by empirical studies of networked systems such as the Internet, social networks, and bio-logical 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 eect, degree distributions, clustering, network correlations, random graph models, models of network growt…
Modeling Extinction
Developed after a meeting at the Santa Fe Institute on extinction modeling, this book comments critically on the various modeling approaches. In the last decade or so, scientists have started to examine a new approach to the patterns of evolution and extinction in the fossil record. This approach may be called "statistical paleontology," since it looks at large-scale patterns in the record and attempts to understand and model their average statis…
Ego-centered networks and the ripple effect
Fast algorithm for detecting community structure in networks
Many networks display community structure--groups of vertices within which connections are dense but between which they are sparser--and sensitive computer algorithms have in recent years been developed for detecting this structure. These algorithms, however, are computationally demanding, which limits their application to small networks. Here we describe an algorithm which gives excellent results when tested on both computer-generated and real-w…
Detecting community structure in networks
Diffusion-based method for producing density-equalizing maps
Map makers have for many years 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 analogous property. Such maps are invaluable for the representation of census results, election returns, disease incidence, and many other kinds of human data. Unfortunately, to scale regions and still have them fit together, one is normally f…
Finding and evaluating community structure in networks
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 definitive features: first, they involve iterative removal of edges from the network to split it into communities, the edges removed being identified using any one of a number of possible "betweenness" measures, and second, these measures are, crucially, recalcul…
Analysis of weighted networks
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 have, by and large, steered clear of such weighted networks, which are often perceived as being harder to analyze than their unweighted counterparts. Here we point out that weighted networks can in many cases be analyzed using a simple mapping from a wei…
Coauthorship networks and patterns of scientific collaboration
By using data from three bibliographic databases in biology, physics, and mathematics, respectively, networks are constructed in which the nodes are scientists, and two scientists are connected if they have coauthored a paper. We use these networks to answer a broad variety of questions about collaboration patterns, such as the numbers of papers authors write, how many people they write them with, what the typical distance between scientists is t…
Finding community structure in very large networks
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 networks because of their computational cost. Here we present a hierarchical agglomeration algorithm for detecting community structure which is faster than many competing algorithms: its running time on a network with n vertices and m edges is O (md lo…
A measure of betweenness centrality based on random walks
Finding community structure in networks using the eigenvectors of matrices
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 to this problem is the maximization of the benefit function known as "modularity" over possible divisions of a network. Here we show that this maximization process can be written in terms of the eigenspectrum of a matrix we call the modularity matrix…
Modularity and community structure in networks
Many networks of interest in the sciences, including social networks, computer networks, and metabolic and regulatory networks, are found to divide naturally into communities or modules. The problem of detecting and characterizing this community structure is one of the outstanding issues in the study of networked systems. One highly effective approach is the optimization of the quality function known as “modularity” over the possible divisions of…
Computer Science (31 works) · Complex Network Analysis Techniques (29 works) · Mathematics (25 works) · Opinion Dynamics and Social Influence (19 works) · Complex network (18 works) · Theoretical Computer Science (17 works) · Artificial Intelligence (13 works) · Graph (13 works) · World Wide Web (13 works) · Physics (12 works)