Network Science Notes - Descriptive Methods of Networks

Statistics for Networks

• Statistical measures provide a macroscopic view of complex systems, allowing researchers to quantify the topology and behavior of networks containing millions of nodes.

Structural Measures for Networks

• Key Descriptive Measures to summarize a graph/network:

  • Order ($n$ or $|V|$): The total number of nodes in the network. It defines the dimensionality of the adjacency matrix ($n \times n$).

  • Size ($m$ or $|E|$): Total number of links or edges. In social networks, this represents the total number of relationships.

  • Edge Limits:

    • For undirected graphs without self-loops: $0 \leq m \leq \frac{n(n-1)}{2}$

    • For directed graphs without self-loops: $0 \leq m \leq n(n-1)$

  • Density ($d$): Measures how close a graph is to being "complete."

    • Sparse Networks: Most real-world networks (like the World Wide Web or social networks) are sparse, where $m \ll n^2$.

    • Dense Networks: Networks where the number of edges approaches the maximum possible value.

    • Formulas:

      • Undirected: $dens(G) = \frac{2m}{n(n-1)}$

      • Directed: $dens(G) = \frac{m}{n(n-1)}$

  • Average Degree ($\langle k \rangle$): The average number of edges connected to a node. For undirected graphs, $\langle k \rangle = \frac{2m}{n}$.

  • Diameter ($D$): The maximum eccentricity of any node in the network. It represents the "longest" shortest path, indicating the maximum distance information must travel to cross the network.

  • Average Path Length ($L$): The mean distance between all pairs of nodes, providing a measure of the network's efficiency in transporting information.

  • Connected Components: Maximal subgraphs where any two vertices are connected by paths.

    • Giant Component: A connected component that contains a significant fraction of the entire network's nodes.

Shortest Path Search and Navigation

• Shortest Path (Geodesic): The path between two nodes such that the sum of the weights of its constituent edges is minimized. In unweighted graphs, this is simply the path with the fewest edges.

• Weight Function ($w$): A mapping $w: E \rightarrow R$ that assigns a numerical value to edges (e.g., distance, cost, time).

• Common Path Problems:

  • Single-Source Shortest Path (SSSP): Finding paths from one source to all other nodes (e.g., GPS routing).

  • All-Pairs Shortest Path (APSP): Finding distances between every node pair to calculate the network diameter.

Algorithms for Shortest Path

1. Dijkstra’s Algorithm:

   • Logic: A greedy algorithm that explores the graph by always choosing the nearest unvisited node.

   • Condition: Only works for graphs with non-negative edge weights.

   • Complexity: $O(|E| + |V| \log |V|)$ with a Fibonacci heap.

2. Bellman-Ford Algorithm:

   • Logic: Relaxes all edges $n-1$ times.

   • Advantage: Handles negative weights and can identify negative cycles, which are paths where the total weight decreases indefinitely.

   • Complexity: $O(|V| \cdot |E|)$.

3. Floyd-Warshall Algorithm:

   • Logic: A dynamic programming approach that builds up shorter paths by considering intermediate nodes.

   • Best for: Small, dense graphs where APSP is needed.

   • Complexity: $O(|V|^3)$.

4. A* Search Algorithm:

   • Logic: An extension of Dijkstra that uses a heuristic function $h(n)$ (estimated cost to goal) to guide the search.

   • Efficiency: Significantly faster for pathfinding in physical space (like video games or maps).

5. Breadth-First Search (BFS):

   • Logic: Explores neighbors layer by layer.

   • Constraint: Only optimal for finding the shortest path in unweighted graphs.

Node-Degree and Distribution Analysis

• Degree ($k$): The number of connections a node has.

  • In-degree ($k_{in}$): Number of incoming edges (measure of prestige/popularity).

  • Out-degree ($k_{out}$): Number of outgoing edges (measure of gregariousness/influence).

• Degree Distribution ($P(k)$): The probability that a randomly selected node has degree $k$.

  • Random Networks (Erdős-Rényi): Follow a Poisson distribution; nodes have a "characteristic" degree.

  • Scale-Free Networks: Follow a Power Law ($P(k) \sim k^{-\gamma}$). Most nodes have small degrees, but a few "hubs" have extremely high degrees.

Network Inequality and Resilience

• Hubs: Highly connected nodes that hold the network together.

  • Small-World Effect: Hubs drastically reduce the average path length (e.g., Six Degrees of Separation).

  • Robustness: Scale-free networks are highly resilient to random node failure but extremely vulnerable to targeted attacks on hubs.

• Lorenz Curve and Gini Coefficient:

  • Lorenz Curve: Plots the cumulative fraction of degrees against the cumulative fraction of nodes.

  • Gini Coefficient ($G$): Calculated as $G = \frac{A}{A+B}$, where $A$ is the area between the Lorenz curve and the line of perfect equality. $G=0$ means everyone has the same degree; $G=1$ means one node has all the edges.

Computational Complexity and Centrality

• Selecting the right measure depends on the scale of the network ($n$).

• Degree Centrality: $O(|V|)$ - Fast, but only considers local connectivity.

• Betweenness Centrality: $O(|V| \cdot |E|)$ (using Brandes' algorithm) - Slow, measures how often a node acts as a bridge along shortest paths.

• Eigenvector Centrality/PageRank: Iteration-based, measures the influence of a node based on the quality of its neighbors.