Network topology and centrality measures are key concepts in understanding complex systems. They help us identify important nodes, analyze network structure, and uncover patterns in connectivity. These tools are crucial for studying everything from social networks to biological systems.

Centrality measures like degree, betweenness, and eigenvector centrality reveal influential nodes. Network structures such as small-world and scale-free networks explain system-wide properties. Local topology measures like clustering coefficient provide insights into community formation and information flow.

Centrality Measures

Degree and Betweenness Centrality

• Degree centrality measures node importance based on number of connections
  • Calculated by counting direct links to other nodes
  • Higher degree centrality indicates more influential or central node
  • Useful for identifying popular or well-connected nodes in social networks
• Betweenness centrality quantifies node's role as intermediary in network
  • Measures frequency a node lies on shortest paths between other nodes
  • Calculated using formula: $C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}$
    • $\sigma_{st}$ represents total number of shortest paths from node s to t
    • $\sigma_{st}(v)$ represents number of those paths passing through v
  • Identifies nodes crucial for information flow or network connectivity
  • High betweenness centrality nodes often serve as bridges between network communities

Closeness and Eigenvector Centrality

• Closeness centrality measures how quickly a node can reach all other nodes
  • Calculated as inverse of sum of shortest path lengths to all other nodes
  • Formula: $C_C(v) = \frac{1}{\sum_{u \neq v} d(u,v)}$
    • $d(u,v)$ represents shortest path distance between nodes u and v
  • Higher closeness centrality indicates more central position in network
  • Useful for identifying nodes with efficient access to entire network
• Eigenvector centrality considers both quantity and quality of connections
  • Assigns relative scores to nodes based on importance of their connections
  • Calculated iteratively using adjacency matrix and eigenvector equation
  • Formula: $Ax = \lambda x$
    • A represents adjacency matrix, x is eigenvector, λ is eigenvalue
  • Useful for identifying influential nodes in networks with varying connection strengths
  • Applied in Google's PageRank algorithm for ranking web pages

Hub and Authority Scores

• Hub and authority scores measure node importance in directed networks
  • Developed as part of HITS (Hyperlink-Induced Topic Search) algorithm
  • Hub score indicates node's effectiveness in pointing to good authorities
  • Authority score reflects quality of information provided by node
• Calculated iteratively using following formulas:
  • Hub score: $h_i = \sum_{j \in O(i)} a_j$
  • Authority score: $a_i = \sum_{j \in I(i)} h_j$
    • O(i) represents set of outgoing links from node i
    • I(i) represents set of incoming links to node i
• Useful for analyzing web page networks and citation networks
• High hub scores identify nodes that link to many authoritative sources
• High authority scores indicate nodes recognized as important by many hubs

Network Structures

Small-World Networks

• Small-world networks combine high clustering with short average path lengths
  • Characterized by most nodes not directly connected, but reachable in few steps
  • Exhibits "six degrees of separation" phenomenon in social networks
• Properties of small-world networks include:
  • High clustering coefficient compared to random networks
  • Low average path length similar to random networks
  • Often modeled using Watts-Strogatz model
    • Starts with regular lattice and rewires connections with probability p
• Examples of small-world networks found in:
  • Neural networks of C. elegans worm
  • Power grids
  • Collaboration networks among scientists
• Efficient for information spread and synchronization processes

Scale-Free Networks

• Scale-free networks characterized by power-law degree distribution
  • Few nodes have many connections (hubs), many nodes have few connections
  • Degree distribution follows formula: $P(k) \sim k^{-γ}$
    • P(k) represents probability of node having k connections
    • γ typically falls between 2 and 3 for real-world networks
• Properties of scale-free networks include:
  • Robustness against random failures
  • Vulnerability to targeted attacks on hubs
  • Presence of "rich-get-richer" phenomenon (preferential attachment)
• Often modeled using Barabási-Albert model
  • New nodes preferentially attach to well-connected existing nodes
• Examples of scale-free networks found in:
  • World Wide Web
  • Protein-protein interaction networks
  • Airline route networks
• Important for understanding growth and resilience of complex systems

Network Motifs

• Network motifs represent recurring, statistically significant subgraphs
  • Act as building blocks of complex networks
  • Identified by comparing subgraph frequencies to randomized networks
• Types of network motifs include:
  • Feed-forward loops
  • Feedback loops
  • Bi-fan motifs
• Significance of network motifs:
  • Provide insights into network function and evolution
  • Help identify functional modules in biological networks
  • Used to compare and classify different types of networks
• Examples of network motifs found in:
  • Transcriptional regulatory networks (feed-forward loops)
  • Neural networks (bi-fan motifs)
  • Food webs (three-node motifs)
• Analyzed using tools like FANMOD and mfinder algorithms

Local Topology

Clustering Coefficient

• Clustering coefficient measures tendency of nodes to form tightly connected groups
  • Quantifies how well a node's neighbors are connected to each other
  • Calculated for individual nodes and entire network
• Local clustering coefficient formula: $C_i = \frac{2e_i}{k_i(k_i-1)}$
  • $e_i$ represents number of edges between neighbors of node i
  • $k_i$ represents degree of node i
• Global clustering coefficient calculated as average of local coefficients
• High clustering coefficient indicates:
  • Presence of tightly knit communities or cliques
  • Potential for efficient local information sharing
• Used to identify modular structures and analyze social networks
  • (Facebook friend networks often show high clustering)

Degree Distribution

• Degree distribution describes probability distribution of node degrees in network
  • Provides insights into overall network structure and connectivity patterns
  • Plotted as histogram or probability density function
• Types of degree distributions include:
  • Poisson distribution (random networks)
  • Power-law distribution (scale-free networks)
  • Exponential distribution
• Analyzing degree distribution reveals:
  • Presence of hubs or highly connected nodes
  • Network's vulnerability to attacks or failures
  • Potential for information spread or disease transmission
• Used to classify networks and understand their growth mechanisms
  • (Internet topology exhibits power-law degree distribution)

Hubs and Authorities

• Hubs and authorities represent highly connected or influential nodes in network
  • Hubs have high out-degree, connecting to many other nodes
  • Authorities have high in-degree, receiving connections from many nodes
• Identification methods for hubs and authorities:
  • Degree centrality (simplest approach)
  • HITS algorithm (more sophisticated, considers link quality)
  • PageRank algorithm (used by Google for web page ranking)
• Importance of hubs and authorities:
  • Critical for network resilience and information flow
  • Targets for interventions in disease spread or marketing campaigns
  • Key players in social influence and opinion formation
• Examples of hubs and authorities in real-world networks:
  • Air travel (hub airports like Atlanta or Frankfurt)
  • Scientific collaboration (highly cited researchers as authorities)
• Analysis of hubs and authorities provides insights into network structure and dynamics