Academic Commons

Articles

Systematic identification of statistically significant network measures

Ziv, Etay; Koytcheff, Robin; Middendorf, Manuel; Wiggins, Chris H.

We present a graph embedding space (i.e., a set of measures on graphs) for performing statistical analyses of networks. Key improvements over existing approaches include discovery of “motif hubs” (multiple overlapping significant subgraphs), computational efficiency relative to subgraph census, and flexibility (the method is easily generalizable to weighted and signed graphs). The embedding space is based on scalars, functionals of the adjacency matrix representing the network. Scalars are global, involving all nodes; although they can be related to subgraph enumeration, there is not a one-to-one mapping between scalars and subgraphs. Improvements in network randomization and significance testing—we learn the distribution rather than assuming Gaussianity—are also presented. The resulting algorithm establishes a systematic approach to the identification of the most significant scalars and suggests machine-learning techniques for network classification.

Subjects

Files

Also Published In

Title
Physical Review E
DOI
https://doi.org/10.1103/PhysRevE.71.016110

More About This Work

Academic Units
Applied Physics and Applied Mathematics
Publisher
American Physical Society
Published Here
September 19, 2014
Academic Commons provides global access to research and scholarship produced at Columbia University, Barnard College, Teachers College, Union Theological Seminary and Jewish Theological Seminary. Academic Commons is managed by the Columbia University Libraries.