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.

• PMID: 15697661
• DOI full text
• PubMed
• PubTator

Reference Type

Journal Article | Research Support, U.S. Gov't, Non-P.H.S. | Research Support, U.S. Gov't, P.H.S.

Authors

Ziv E, Koytcheff R, Middendorf M, Wiggins C

Primary Lit For

Additional Lit For

Review For