Key Node Mining

Key Node Mining (Part 1)

1. What Is Key Node Mining?

1. The Fragile Internet

If you remove the top 2% of nodes — e.g. Baidu, Tencent — many other nodes become unusable.

2. Efficient but Fragile Power Grids

Interconnection improves efficiency and cuts cost, but failures propagate through the system.

Common characteristics (networks):

• Many individuals; some are more important than others
• Individuals are interconnected

3. Social Networks

Ordinary users and influential accounts (e.g. Weibo celebrities).

4. Collaboration Networks

When scientists co-author a paper or a book, the network reveals who has greater influence.

5. Transportation Networks

Train routes, flight routes, commute paths — e.g. studying flight networks to infer city importance.

6. Financial Investment Networks

Investment ties among firms and banks resemble power systems: when one firm has economic trouble, risk spreads to other nodes. This helps predict financial risk and crises.

2. Basic Terms and Application Scenarios

Node Importance Metrics (Centrality)

Structural metrics based on neighbors; path-based metrics; iterative optimization metrics; metrics based on node removal and contraction.

Typical Applications

• Identifying super-spreaders in networks
• Predicting important proteins
• Measuring academic influence
• Detecting financial risk
• Predicting career trajectories
• Predicting software failures

Key Node Mining (Part 2): Structural Metrics Based on Neighbors

Understanding Networks

• Nodes: people, firms, animals, proteins, etc.
• Edges: relationships between nodes; directed (e.g. investment) or undirected (e.g. collaboration)
• Degree: number of connections to a node
• General pattern: social networks follow a power-law degree distribution — most users have very low degree, but a few hubs have very high degree. Degree distribution is uneven.
• Problem: a neighbor’s propagation ability may matter more than raw count
• Reformulation: how many neighbors does a node have → how many high-quality neighbors — measured by the H-index

H-Index

Example: Scholar A published 100 papers; Scholar B published 50, but B’s citations are higher — B has greater academic impact.

Definition: a scholar’s H-index is h iff they have at most h papers each cited at least h times.

Operator: y = H(x₁, x₂, …, xₙ)

A node v’s H-metric: v = H(k₁, k₂, …, kᵢ)

A node’s H-index is h iff it has at most h neighbors each with degree at least h.

H-family: degree is the 0th-order H-index (h = k); first-order H-index is the formula above; as n → ∞, the nth-order H-index converges to the core number.

Core Number

Remove all degree-1 nodes, call that k₁; remove all degree-2 nodes, call that k₂; remove all degree-3 nodes, call that k₃; … when no nodes remain, the network’s core number is three. Nodes in k₃ are more important — k-shell decomposition, the “peel the onion” method.

Application: information propagation — pick a node as the source; information spreads along edges; higher core number → wider spread.

Clustering Coefficient

When neighbors are tightly connected, information circulates locally; high clustering limits breadth of propagation.

Clustering coefficient: connections among neighbors, excluding the maximum possible.

Communities

Members of a community are densely connected internally. When placing multiple information sources in different communities, community count matters.

Community count is not always effective — when communities are unclear:

Key Node Mining (Part 3): Path-Based Structural Metrics

Paths

Complete graph: every pair of nodes is connected. A path is a node sequence from one node to another; shortest paths are often preferred.

Shortest-Path Algorithms

Eccentricity: Maximum Distance

Closeness centrality:

Betweenness Centrality

How important a node is on shortest paths. If shortest paths between any two communities pass through this node, it is important. Computationally expensive.

Adjacency Matrix A

Symmetric matrix; row sums equal node degrees. A×A counts paths of length 2; A×A×A counts paths of length 3.

Katz Centrality: All Paths Considered

Subgraph Centrality

Number of paths from a node back to itself.

Key Node Mining (Part 4): Iterative Optimization Metrics

Idea: a node’s importance depends on its neighbors’ importance. Algorithms differ in how neighbor influence is weighted.

Eigenvector Centrality

A node’s centrality is proportional to the sum of its neighbors’ centralities.

• Problem 1: high-degree nodes self-reinforce strongly. Fix 1: non-backtracking matrix.
• Problem 2: slow convergence. Fix: cumulative nomination.

Non-Backtracking Matrix

Prevents double-counting; higher complexity.

Difference after adding non-backtracking:

PageRank

A variant of eigenvector centrality for ranking web page quality.

Basic idea: the more important pages link to a page, the more important that page is.

Background: random walk — from maze wandering to web surfing. Iteration: from random walk to PageRank, with random jumps and damping.

LeaderRank

Introduces a super-node to address trap problems:

HITS Algorithm

Hub and authority properties of web pages:

• An authority page is pointed to by many high-quality hubs
• A high-quality hub (e.g. Baidu) points to many high-quality authority pages

Each iteration requires normalization; otherwise convergence fails.

Key Node Mining (Part 5): Metrics Based on Node Removal and Contraction

Connectivity-Sensitivity Methods

• Size of the largest connected component
• Number of connected components
• Average distance between nodes
• Change in distances from removed nodes to others
• Change in distances among removed nodes
• Change in distances among remaining nodes after removal

Stability-Sensitivity Methods

The more important a node, the greater the damage when it is removed.

Residual Closeness Centrality

Node-disjoint paths:

Paths that share no intermediate nodes.

Node Contraction

Contract a node and its neighbors into one new node — a tighter condensation.

How to Measure Cohesion?

Node count times the inverse of average distance.

Change in cohesion: