Statistical and Machine Learning Approaches for Network Analysis -- Contents -- Preface -- Contributors -- 1 A Survey of Computational Approaches to Reconstruct and Partition Biological Networks -- 1.1 INTRODUCTION -- 1.2 BIOLOGICAL NETWORKS -- 1.2.1 Directed Networks -- 1.2.2 Undirected Networks -- 1.3 GENOME-WIDE MEASUREMENTS -- 1.3.1 Gene Expression Data -- 1.3.2 Gene Sets -- 1.4 RECONSTRUCTION OF BIOLOGICAL NETWORKS -- 1.4.1 Reconstruction of Directed Networks -- 1.4.1.1 Boolean Networks -- 1.4.1.2 Probabilistic Boolean Networks -- 1.4.1.3 Bayesian Networks -- 1.4.1.4 Collaborative Graph Model -- 1.4.1.5 Frequency Method -- 1.4.1.6 EM-Based Inference from Gene Sets -- 1.4.2 Reconstruction of Undirected Networks -- 1.4.2.1 Relevance Networks -- 1.4.2.2 Graphical Gaussian Models -- 1.5 PARTITIONING BIOLOGICAL NETWORKS -- 1.5.1 Directed and Undirected Networks -- 1.5.2 Partitioning Undirected Networks -- 1.5.2.1 Kernighan-Lin Algorithm -- 1.5.2.2 Girvan-Newman Algorithm -- 1.5.2.3 Newman's Eigenvector Method -- 1.5.2.4 Infomap -- 1.5.2.5 Clique Percolation Method -- 1.5.3 Partitioning Directed Networks -- 1.5.3.1 Newman's Eigenvector Method -- 1.5.3.2 Infomap -- 1.5.3.3 Clique Percolation Method -- 1.6 DISCUSSION -- REFERENCES -- 2 Introduction to Complex Networks: Measures, Statistical Properties, and Models -- 2.1 INTRODUCTION -- 2.2 REPRESENTATION OF NETWORKS -- 2.3 CLASSICAL NETWORK -- 2.3.1 Random Network -- 2.3.2 Lattice Network -- 2.4 SCALE-FREE NETWORK -- 2.4.1 Degree Distribution -- 2.4.2 Degree Distribution of Random Network -- 2.4.3 Power-Law Distribution in Real-World Networks -- 2.4.4 Barabási-Albert Model -- 2.4.5 Configuration Model -- 2.5 SMALL-WORLD NETWORK -- 2.5.1 Average Shortest Path Length -- 2.5.2 Ultrasmall-World Network -- 2.6 CLUSTERED NETWORK -- 2.6.1 Clustering Coefficient -- 2.6.2 Watts-Strogatz Model.

2.7 HIERARCHICAL MODULARITY -- 2.7.1 Hierarchical Model -- 2.7.2 Dorogovtsev-Mendes-Samukhin Model -- 2.8 NETWORK MOTIF -- 2.9 ASSORTATIVITY -- 2.9.1 Assortative Coefficient -- 2.9.2 Degree Correlation -- 2.9.3 Linear Preferential Attachment Model -- 2.9.4 Edge Rewiring Method -- 2.10 RECIPROCITY -- 2.11 WEIGHTED NETWORKS -- 2.11.1 Strength -- 2.11.2 Weighted Clustering Coefficient -- 2.11.3 Weighted Degree Correlation -- 2.12 NETWORK COMPLEXITY -- 2.13 CENTRALITY -- 2.13.1 Definition -- 2.13.2 Comparison of Centrality Measures -- 2.14 CONCLUSION -- REFERENCES -- 3 Modeling for Evolving Biological Networks -- 3.1 INTRODUCTION -- 3.2 UNIFIED EVOLVING NETWORK MODEL: REPRODUCTION OF HETEROGENEOUS CONNECTIVITY, HIERARCHICAL MODULARITY, AND DISASSORTATIVITY -- 3.2.1 Network Model -- 3.2.2 Degree Distribution -- 3.2.3 Degree-Dependent Clustering Coefficient -- 3.2.4 Average Clustering Coefficient -- 3.2.5 Degree Correlation -- 3.2.6 Assortative Coefficient -- 3.2.7 Comparison with Real Data -- 3.3 MODELING WITHOUT PARAMETER TUNING: A CASE STUDY OF METABOLIC NETWORKS -- 3.3.1 Network Model -- 3.3.2 Analytical Solution -- 3.3.3 Estimation of the Parameters -- 3.3.4 Comparison with Real Data -- 3.4 BIPARTITE RELATIONSHIP: A CASE STUDY OF METABOLITE DISTRIBUTION -- 3.4.1 Structural Properties of Metabolite Distributions -- 3.4.2 Bipartite Network Model -- 3.4.3 Comparison with Real Data -- 3.4.4 Related Model -- 3.5 CONCLUSION -- REFERENCES -- 4 Modularity Configurations in Biological Networks with Embedded Dynamics -- 4.1 INTRODUCTION -- 4.1.1 Biological Networks and Computational Challenges -- 4.1.2 Outline -- 4.2 METHODS -- 4.2.1 General Approach -- 4.2.2 PIN Fragmentation -- 4.2.3 PIN Topology -- 4.2.3.1 Modularity by Communities -- 4.2.3.2 Modularity by Cores -- 4.3 RESULTS -- 4.3.1 Community Maps -- 4.3.1.1 Analysis -- 4.3.2 Core Structures.

4.3.3 On Network Entropy -- 4.4 DISCUSSION AND CONCLUDING REMARKS -- ACKNOWLEDGMENT -- SUPPORTING INFORMATION -- REFERENCES -- 5 Influence of Statistical Estimators on the Large-Scale Causal Inference of Regulatory Networks -- 5.1 INTRODUCTION -- 5.2 METHODS -- 5.2.1 C3NET -- 5.2.1.1 C3NET (Conservative Causal Core) -- 5.2.2 Estimating Mutual Information -- 5.2.3 Global Measures -- 5.2.4 Ensemble Data and Local Network-Based Measures -- 5.2.5 Local Network-Based Measures -- 5.2.6 Network Structure -- 5.3 RESULTS -- 5.3.1 Global Network Inference Performance -- 5.3.2 Local Network Inference Performance -- 5.4 CONCLUSION AND SUMMARY -- ACKNOWLEDGMENT -- REFERENCES -- 6 Weighted Spectral Distribution: A Metric for Structural Analysis of Networks -- 6.1 INTRODUCTION -- 6.2 WEIGHTED SPECTRAL DISTRIBUTION -- 6.3 A SIMPLE WORKED EXAMPLE -- 6.4 THE INTERNET AUTONOMOUS SYSTEM TOPOLOGY -- 6.4.1 Characterization -- 6.4.2 Generation -- 6.4.3 Observations -- 6.5 COMPARING TOPOLOGY GENERATORS -- 6.5.1 Methodology -- 6.5.2 Topological Metrics -- 6.5.3 Discussion -- 6.6 TUNING TOPOLOGY GENERATOR PARAMETERS -- 6.6.1 Link Densities -- 6.6.2 Spectra PDF -- 6.6.3 Limitations of Spectra PDF -- 6.6.4 Weighted Spectra -- 6.6.5 Weighted Spectra Comparison -- 6.7 GENERATING TOPOLOGIES WITH OPTIMUM PARAMETERS -- 6.8 INTERNET TOPOLOGY EVOLUTION -- 6.9 CONCLUSIONS -- REFERENCES -- 7 The Structure of an Evolving Random Bipartite Graph -- 7.1 INTRODUCTION -- 7.2 THE STRUCTURE OF A SPARSE BIPARTITE GRAPH -- 7.3 ENUMERATING BIPARTITE GRAPHS -- 7.4 ASYMPTOTIC EXPANSION VIA THE SADDLE POINT METHOD -- 7.5 PROOFS OF THE MAIN THEOREMS -- 7.6 EMPIRICAL DATA -- 7.7 CONCLUSION AND SUMMARY -- REFERENCES -- 8 Graph Kernels -- 8.1 INTRODUCTION -- 8.1.1 Kernel Learning in a Nutshell -- 8.1.2 Graph Kernels -- 8.1.3 Computational Considerations -- 8.2 CONVOLUTION KERNELS -- 8.2.1 Definition.

8.2.2 Variants and Extensions -- 8.3 RANDOM WALK GRAPH KERNELS -- 8.3.1 Definition -- 8.3.2 Computation -- 8.3.3 Variants and Extensions -- 8.4 PATH-BASED GRAPH KERNELS -- 8.4.1 Definition and Computation -- 8.4.2 Variants and Extensions -- 8.5 TREE-PATTERN GRAPH KERNELS -- 8.5.1 Definition -- 8.5.2 Computation -- 8.5.3 Variants and Extensions -- 8.6 CYCLIC PATTERN KERNELS -- 8.6.1 Definition -- 8.6.2 Computation -- 8.6.3 Variants and Extensions -- 8.7 GRAPHLET KERNELS -- 8.7.1 Definition -- 8.7.2 Computation -- 8.7.3 Variants and Extensions -- 8.8 OPTIMAL ASSIGNMENT KERNELS -- 8.8.1 Definition -- 8.8.2 Computation -- 8.8.3 Variants and Extensions -- 8.9 OTHER GRAPH KERNELS -- 8.10 APPLICATIONS IN BIO- AND CHEMINFORMATICS -- 8.11 SUMMARY AND CONCLUSIONS -- ACKNOWLEDGMENTS -- REFERENCES -- 9 Network-Based Information Synergy Analysis for Alzheimer Disease -- 9.1 INTRODUCTION -- 9.2 DATASETS AND METHODS -- 9.2.1 Microarray Dataset and Protein-Protein Interaction Data -- 9.2.2 Calculation of the Synergy Scores of Gene Pairs -- 9.2.3 Permutation Test to Evaluate the Significance of the Synergy -- 9.2.4 Characterization of the Network Topology -- 9.3 RESULTS -- 9.3.1 Information Synergy for Simulated Gene Pairs -- 9.3.2 Topological Characteristics of Synergy Network for AD -- 9.3.3 Differential Expression and Correlation Patterns for the Pairs in Synergy Network -- 9.3.4 Hub Genes in the Positive Synergy Network -- 9.4 SUMMARY AND CONCLUSIONS -- ACKNOWLEDGMENT -- REFERENCES -- 10 Density-Based Set Enumeration in Structured Data -- 10.1 INTRODUCTION -- 10.2 UNSUPERVISED PATTERN DISCOVERY IN STRUCTURED DATA -- 10.2.1 Graph Mining -- 10.2.2 Optimal Subgraph Search -- 10.2.3 Graph Clustering -- 10.2.4 Bicluster Analysis -- 10.2.5 Itemset Mining -- 10.2.6 Relational Data Mining and Higher-Order Association Analysis.

10.3 DENSE CLUSTER ENUMERATION IN WEIGHTED INTERACTION NETWORKS -- 10.3.1 Notation and Problem Definition -- 10.3.2 Enumeration Algorithm -- 10.3.2.1 Search Space -- 10.3.2.2 Reduction Scheme -- 10.3.2.3 Search Procedure -- 10.3.3 Efficient Generation of Children -- 10.3.4 Complexity -- 10.3.5 Output Representation -- 10.3.5.1 Locally Maximal Clusters -- 10.3.5.2 Cluster Ranking -- 10.3.6 Degree-Based Cluster Criteria -- 10.3.6.1 Minimum Degree -- 10.3.7 Minimum Relative Degree and Quasi-Cliques -- 10.3.7.1 Approaches to Quasi-Clique Mining -- 10.3.8 Integration of Node Weights -- 10.3.9 Constraint Integration -- 10.3.9.1 Constraints from External Data Sources -- 10.3.9.2 Connectivity Constraints -- 10.3.9.3 Cardinality and Branching Restrictions -- 10.4 DENSE CLUSTER ENUMERATION IN HIGHER-ORDER ASSOCIATION DATA -- 10.4.1 Motivation -- 10.4.2 Problem Definition -- 10.4.3 Enumeration Approach -- 10.4.3.1 Global Index Representation -- 10.4.3.2 Search Space -- 10.4.3.3 Reduction Scheme -- 10.4.3.4 Search Algorithm -- 10.4.3.5 Symmetry Adaptations -- 10.5 DISCUSSION -- REFERENCES -- 11 Hyponym Extraction Employing a Weighted Graph Kernel -- 11.1 INTRODUCTION -- 11.2 RELATED WORK -- 11.3 DRAWBACKS OF CURRENT APPROACHES -- 11.4 SEMANTIC NETWORKS FOLLOWING THE MULTINET FORMALISM -- 11.5 SUPPORT VECTOR MACHINES AND KERNELS -- 11.6 ARCHITECTURE -- 11.7 GRAPH KERNEL -- 11.8 GRAPH KERNEL EXTENSIONS -- 11.9 DISTANCE WEIGHTING -- 11.10 FEATURES FOR HYPONYMY EXTRACTION -- 11.11 EVALUATION -- 11.12 CONCLUSION AND OUTLOOK -- ACKNOWLEDGMENTS -- REFERENCES -- Index.