Quantitative Measures Of

NETWORK COMPLEXITY 191 Danail Bonchev and Gregory A. Buck

1. Some History 191

2. Networks as Graphs 193

2.1. Basic notions in graph theory [36-38] 193

2.2. Adjacency matrix and related graph descriptors 195

2.3. Cluster coefficient and extended connectivity 196

2.4. Graph distances 198

2.5. Weighted graphs 201

3. How to Measure Network Complexity 202

3.1. Careful with symmetry! 202

3.2. Can Shannon's information content measure topological complexity? 203

3.3. Global, average, and normalized complexity 205

3.4. The subgraph count, SC, and its components 207

3.5. Overall connectivity, OC 210

3.6. The total walk count, TWC 211

4. Combined Complexity Measures Based on the

Graph Adjacency and Distance 213

4.2. The complexity index B 215

5. Vertex Accessibility and Complexity of Directed Graphs . . . 218

6. Complexity Estimates of Biological and Ecological Networks 221

6.1. Networks of Protein Complexes 222

6.2. Food webs 226

7. Overview 230

Acknowledgement 232

References 232

Was this article helpful?

0 0

Post a comment