Systematic identification of statistically significant network measures

作     者：Etay Ziv Robin Koytcheff Manuel Middendorf Chris Wiggins 

作者机构：College of Physicians and Surgeons Columbia University New York New York 10027 USA Department of Biomedical Engineering Columbia University New York New York 10027 USA Department of Applied Physics and Applied Mathematics Columbia University New York New York 10027 USA Department of Physics Columbia University New York New York 10027 USA Center for Computational Biology and Bioinformatics Columbia University New York New York 10027 USA 

出 版 物：《Physical Review E》 (物理学评论E辑：统计、非线性和软体物理学)

年 卷 期：2005年第71卷第1期

页      面：016110-016110页

核心收录：

学科分类：07[理学] 070203[理学-原子与分子物理] 0702[理学-物理学] 

基　　金：National Institute of General Medical Sciences, NIGMS, (R01GM036277) National Institute of General Medical Sciences, NIGMS 

主　　题：ESCHERICHIA-COLI TRANSCRIPTIONAL REGULATION COMPLEX NETWORKS PROTEIN ORGANIZATION SPECIFICITY GRAPHS MOTIFS OPERON 

摘      要：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.