Large Scale Structure and Dynamics of Complex Networks

The following sections are included:

• Preface

• Contents

Various types of diverse networks — communication networks, transport networks, global business networks, networks of friends, or the Internet — shape our daily life and the way we think and act. We depend on various social, economic, and technological networks that weave a tissue of businesses, governments, technologies and that contain us as citizens, users, or customers. We only become aware of our dependence if failures occur in these networks: when cities are plunged into darkness because of a breakdown of the power grid like happened recently in New York, when national economies collapse because of a failure of global financial systems like happened in the South-Asian banking crisis, or when computer viruses spread with mind-boggling speed over information networks destroying or, even worse, exposing sensitive data.

The following sections are included:

• Introduction

• Basic definitions

• Different kinds of graphs
  • Weighted, directed and oriented graphs
  • Subgraphs
  • Partited graphs

• Paths and cycles
  • Trees

• Statistics on graphs
  • Small world properties
  • Clustering coefficient
  • Degree distribution

• Complexity

• What is next

The following sections are included:

• Introduction

• Random networks
  • Erdős-Rényi networks
  • Fitness networks

• Preferential attachment networks
  • The Barabási-Albert model
  • Duplication-divergence models
  • Growing weighted networks

• The small-world model

• Outlook

The following sections are included:

• Introduction

• Detailed balance condition

• Empirical measurement of correlations
  • Two vertices correlations: ANND
  • Three vertices correlations: Clustering

• Networks in the real world
  • Pretty-good-privacy web of trust

• Modeling correlations
  • Disassortative correlations
  • The configuration model
  • Growing models
  • Assortativity generators
  • Modeling clustered networks
  • Random graphs with attributes
  • Hidden color models
  • Fitness or hidden variables models
  • Fitness and preferential attachment models

• Outlook

The following sections are included:

• Introduction

• Tools for the characterization of weighted networks
  • Weights
  • Degree and weight distributions
  • Weighted degree: Strength
  • Weighted clustering
  • Weighted assortativity: Affinity
  • Local heterogeneity

• Weighted networks: Empirical results
  • Transportation networks
  • Airport network
  • Urban and inter-urban movement networks
  • Transportation networks: Summary
  • Social network: Example of the scientific collaboration network
  • Biological network: The case of the metabolic network

• Modeling weighted networks
  • Coupling weight and topology
  • A simple model: Weight perturbation and “busy get busier” effects
  • Local heterogeneities, nonlinearities and space-topology coupling
  • Other models coupling traffic and topology

• Outlook

The following sections are included:

• Introduction

• Definitions of communities

• Evaluating community identification

• Link removal methods
  • Shortest path centrality

• Current-flow and random walk centrality
  • Information centrality
  • Link clustering

• Agglomerative methods
  • Hierarchical clustering
  • L-shell method

• Methods based on maximising modularity
  • Greedy algorithm
  • Simulated annealing methods
  • Extremal optimisation

• Spectral analysis methods
  • Spectral bisection
  • Multi dimensional spectral analysis
  • Constrained optimisation
  • Approximate resistance networks

• Other methods
  • Clustering and curvature
  • Random walk based methods
  • Q-potts model

• Comparative evaluation

• Conclusion

The following sections are included:

• Introduction

• Global methods for visualizing large graphs
  • Spring embedder based methods
  • Properties
  • Spectral layout
  • Properties

• Analytical layouts
  • Centrality and status layouts
  • Clustered layouts
  • Case studies

The following sections are included:

• Introduction

• Preliminaries

• WebBase
  • In-degree and out-degree
  • PageRank
  • Bipartite cliques
  • Strongly connected components

• Stochastic models of the webgraph
  • Models of the webgraph
  • A multi-layer model
  • Large scale simulation

• Algorithmic techniques for generating and measuring webgraphs
  • Data representation and multifiles
  • Generating webgraphs
  • Traversal with two bits for each node
  • Semi-external breadth first search
  • Semi-external depth first search
  • Computation of the SCCs
  • Computation of the bow-tie regions
  • Disjoint bipartite cliques
  • PageRank

• Summary and outlook

The following sections are included:

• Introduction

• Internet maps

• Heavy tailed distributions

• Sampling biases and the scale-free nature of the Internet

• Hierarchies and correlations

• Outlook

The following sections are included:

• Introduction

• Graph-theoretical formalism
  • Basic notions
  • Connected subgraphs and minimum spanning trees

• Graphs and spanning trees in ecology
  • Spanning trees in food webs
  • Spanning trees in taxonomy

• Empirical results
  • Food webs
  • Taxonomic trees

• Summary and outlook

The following sections are included:

• Introduction

• Social networks: Examples and general features

• Degree distribution
  • Open questions on degree distribution

• Assortativity
  • Open questions on assortativity

• Clustering
  • Open questions on clustering

• Community structure
  • Open questions on community structure

• Economical networks: The case-study of the board of directors
  • Board and directors network as bipartite graphs

• Topological properties of boards and directors Networks
  • Average quantities
  • Degree distributions and assortativity
  • Lobbies

• Modeling boards of directors networks
  • Interlock structure and decision making dynamics
  • Single board decision making model
  • Multiple boards decision making model

• Conclusion

The following sections are included:

• References

• Index