John I. Moore

Purdue University West Lafayette

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Trends

Author Order

Document Type

Co-Authors

William T. Trotter

Georgia Institute of Technology

Jennifer Neville

Microsoft (United States)

Joseph J. Pfeiffer

Purdue University West Lafayette

W. T. Trotter

Georgia Institute of Technology

Stephen Mussmann

University of Washington

David P. Sumner

University of South Carolina

Cooperative Institutions

Purdue University West Lafayette

Microsoft (United States)

Microsoft Research (United Kingdom)

Georgia Institute of Technology

Arizona State University

Core Competence

University of South Carolina

Royal Holloway University of London

University of Birmingham

Universidad Univer

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Field

Incorporating Assortativity and Degree Dependence into Scalable Network Models

Proceedings of the AAAI Conference on Artificial Intelligence (2015)

Stephen Mussmann John I. Moore Joseph J. Pfeiffer Jennifer Neville

Due to the recent availability of large complex networks, considerable analysis has focused on understanding and characterizing the properties of these networks. Scalable generative graph models focus on modeling distributions of graphs that match real world network properties and scale to large datasets. Much work has focused on modeling networks with a power law degree distribution, clustering, and small diameter. In network analysis, the assortativity statistic is defined as the correlation between the degrees of linked nodes in the network. The assortativity measure can distinguish between types of networks---social networks commonly exhibit positive assortativity, in contrast to biological or technological networks that are typically disassortative. Despite this, little work has focused on scalable graph models that capture assortativity in networks. The contributions of our work are twofold. First, we prove that an unbounded number of pairs of networks exist with the same degree distribution and assortativity, yet different joint degree distributions. Thus, assortativity as a network measure cannot distinguish between graphs with complex (non-linear) dependence in their joint degree distributions. Motivated by this finding, we introduce a generative graph model that explicitly estimates and models the joint degree distribution. Our Binned Chung Lu method accurately captures both the joint degree distribution and assortativity, while still matching characteristics such as the degree distribution and clustering coefficients. Further, our method has subquadratic learning and sampling methods that enable scaling to large, real world networks. We evaluate performance compared to other scalable graph models on six real world networks, including a citation network with over 14 million edges.

Assortativity

Degree distribution

Clustering coefficient

Degree (music)

Generative model

10.1609/aaai.v29i1.9207

Cite

Citations (12)

The Dimension of a Comparability Graph

Proceedings of the American Mathematical Society (1976)

W. T. Trotter John I. Moore David P. Sumner

Dushnik and Miller defined the dimension of a partial order P as the minimum number of linear orders whose intersection is P. Ken Bogart asked if the dimension of a partial order is an invariant of the associated comparability graph. In this paper we answer Bogartâs question in the affirmative. The proof involves a characterization of the class of comparability graphs defined by Aigner and Prins as uniquely partially orderable graphs. Our characterization of uniquely partially orderable graphs is another instance of the frequently encountered phenomenon where the obvious necessary condition is also sufficient.

Comparability

Comparability graph

10.2307/2041106

Cite

Citations (12)

The dimension of planar posets

Journal of Combinatorial Theory Series B (1977)

William T. Trotter John I. Moore

Hasse diagram

10.1016/0095-8956(77)90048-x

Cite

Citations (106)

Assortativity in Chung Lu Random Graph Models

Stephen Mussmann John I. Moore Joseph J. Pfeiffer Jennifer Neville

Due to the widespread interest in networks as a representation to investigate the properties of complex systems, there has been a great deal of interest in generative models of graph structure that can capture the properties of networks observed in the real world. Recent models have focused primarily on accurate characterization of sparse networks with skewed degree distributions, short path lengths, and local clustering. While assortativity---degree correlation among linked nodes---is used as a measure to both describe and evaluate connectivity patterns in networks, there has been little effort to explicitly incorporate patterns of assortativity into model representations. This is because many graph models are edge-based (modeling whether a link should be placed between a pair of nodes i and j) and assortativity is a second-order characteristic that depends on the global properties of the graph (i.e., the final degree of i and j). As such, it is difficult to incorporate direct optimization of assortativity into edge-based generative models.

Assortativity

Generative model

Clustering coefficient

Degree (music)

Graphical model

10.1145/2659480.2659495

Cite

Citations (8)

Some theorems on graphs and posets

Discrete Mathematics (1976)

William T. Trotter John I. Moore

Lattice (music)

Ordered set

10.1016/0012-365x(76)90111-4

Cite

Citations (32)

The dimension of a comparability graph

Proceedings of the American Mathematical Society (1976)

W. T. Trotter John I. Moore David P. Sumner

Dushnik and Miller defined the dimension of a partial order P as the minimum number of linear orders whose intersection is P. Ken Bogart asked if the dimension of a partial order is an invariant of the associated comparability graph.In this paper we answer Bogart's question in the affirmative.The proof involves a characterization of the class of comparability graphs defined by Aigner and Prins as uniquely partially orderable graphs.Our characterization of uniquely partially orderable graphs is another instance of the frequently encountered phenomenon where the obvious necessary condition is also sufficient.

Comparability

10.1090/s0002-9939-1976-0417001-6

Cite

Citations (53)

Interval hypergraphs and D-interval hypergraphs

Discrete Mathematics (1977)

John I. Moore

Hypergraph

10.1016/0012-365x(77)90148-0

Cite

Citations (12)

Characterization problems for graphs, partially ordered sets, lattices, and families of sets