java.lang.Object

cloud.opencode.base.graph.algorithm.CentralityUtil

public final class CentralityUtil extends Object

Centrality Util - Graph Centrality Algorithms 中心性工具类 - 图中心性算法

Utility class providing various centrality measures for graphs.

提供图的各种中心性度量的工具类。

Supported Metrics | 支持的指标:

Degree Centrality - 度中心性
Closeness Centrality - 接近中心性
Betweenness Centrality - 中介中心性
PageRank - PageRank算法
Eigenvector Centrality - 特征向量中心性
Katz Centrality - Katz中心性

Features | 主要功能:

Degree, closeness, and betweenness centrality - 度、接近和中介中心性
PageRank with configurable damping factor - 可配置阻尼因子的PageRank
Eigenvector and Katz centrality - 特征向量和Katz中心性
Top-k central vertex extraction - 前k个中心顶点提取

Usage Examples | 使用示例:

// Degree centrality
Map<String, Double> degree = CentralityUtil.degreeCentrality(graph);

// PageRank
Map<String, Double> pageRank = CentralityUtil.pageRank(graph, 0.85, 100);

// Betweenness centrality
Map<String, Double> betweenness = CentralityUtil.betweennessCentrality(graph);

// Find top-k central vertices
List<String> topVertices = CentralityUtil.topKCentral(graph, 5, CentralityUtil::pageRank);

Security | 安全性:

Thread-safe: Yes (stateless utility class) - 线程安全: 是（无状态工具类）
Null-safe: Yes (returns empty results for null inputs) - 空值安全: 是（null输入返回空结果）

Performance | 性能特性:

Time complexity: O(V * (V + E)) for betweenness centrality - 时间复杂度: O(V * (V + E))（中介中心性）
Space complexity: O(V^2) - 空间复杂度: O(V^2)

Since:

JDK 25, opencode-base-graph V1.0.0

Author:

Leon Soo www.LeonSoo.com

See Also:

Nested Class Summary

Nested Classes

Modifier and Type

Class

Description

static final record

CentralityUtil.CentralityStats

Centrality statistics record.
Field Summary

Fields

Modifier and Type

Field

Description

static final double

DEFAULT_DAMPING_FACTOR

Default damping factor for PageRank | PageRank默认阻尼因子

static final int

DEFAULT_MAX_ITERATIONS

Default maximum iterations | 默认最大迭代次数

static final double

DEFAULT_TOLERANCE

Default convergence threshold | 默认收敛阈值
Method Summary

Modifier and Type

Method

Description

static <V> Map<V,Double>

betweennessCentrality(Graph<V> graph)

Calculate betweenness centrality for all vertices.

static <V> Map<V,Double>

betweennessCentrality(Graph<V> graph, boolean normalized)

Calculate betweenness centrality with optional normalization.

static <V> Map<V,Double>

closenessCentrality(Graph<V> graph)

Calculate closeness centrality for all vertices.

static <V> Map<V,Double>

degreeCentrality(Graph<V> graph)

Calculate degree centrality for all vertices.

static <V> Map<V,Double>

eigenvectorCentrality(Graph<V> graph)

Calculate eigenvector centrality for all vertices.

static <V> Map<V,Double>

eigenvectorCentrality(Graph<V> graph, int maxIterations, double tolerance)

Calculate eigenvector centrality with parameters.

static <V> CentralityUtil.CentralityStats

getStats(Map<V,Double> centrality)

Get centrality statistics.

static <V> Map<V,Double>

inDegreeCentrality(Graph<V> graph)

Calculate in-degree centrality for directed graphs.

static <V> Map<V,Double>

katzCentrality(Graph<V> graph, double alpha, double beta)

Calculate Katz centrality for all vertices.

static <V> Map<V,Double>

katzCentrality(Graph<V> graph, double alpha, double beta, int maxIterations, double tolerance)

Calculate Katz centrality with full parameters.

static <V> Map<V,Double>

normalize(Map<V,Double> centrality)

Normalize centrality values to [0, 1] range.

static <V> Map<V,Double>

outDegreeCentrality(Graph<V> graph)

Calculate out-degree centrality for directed graphs.

static <V> Map<V,Double>

pageRank(Graph<V> graph)

Calculate PageRank for all vertices using default parameters.

static <V> Map<V,Double>

pageRank(Graph<V> graph, double dampingFactor, int maxIterations)

Calculate PageRank for all vertices.

static <V> Map<V,Double>

pageRank(Graph<V> graph, double dampingFactor, int maxIterations, double tolerance)

Calculate PageRank with convergence tolerance.

static <V> List<V>

topK(Map<V,Double> centrality, int k)

Get the top-K most central vertices.

Methods inherited from class Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details
- DEFAULT_DAMPING_FACTOR
  public static final double DEFAULT_DAMPING_FACTOR
  
  Default damping factor for PageRank | PageRank默认阻尼因子
  
  See Also:
  
  Constant Field Values
- DEFAULT_MAX_ITERATIONS
  public static final int DEFAULT_MAX_ITERATIONS
  
  Default maximum iterations | 默认最大迭代次数
  
  See Also:
  
  Constant Field Values
- DEFAULT_TOLERANCE
  public static final double DEFAULT_TOLERANCE
  
  Default convergence threshold | 默认收敛阈值
  
  See Also:
  
  Constant Field Values
Method Details
- degreeCentrality
  
  public static <V> Map<V,Double> degreeCentrality(Graph<V> graph)
  
  Calculate degree centrality for all vertices. 计算所有顶点的度中心性。
  Degree centrality is the number of edges connected to a vertex, normalized by the maximum possible degree (n-1).
  
  度中心性是与顶点相连的边数，按最大可能度数(n-1)归一化。
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the graph | 图
  
  Returns:
  
  map of vertex to degree centrality | 顶点到度中心性的映射
- inDegreeCentrality
  
  public static <V> Map<V,Double> inDegreeCentrality(Graph<V> graph)
  
  Calculate in-degree centrality for directed graphs. 计算有向图的入度中心性。
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the graph | 图
  
  Returns:
  
  map of vertex to in-degree centrality | 顶点到入度中心性的映射
- outDegreeCentrality
  
  public static <V> Map<V,Double> outDegreeCentrality(Graph<V> graph)
  
  Calculate out-degree centrality for directed graphs. 计算有向图的出度中心性。
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the graph | 图
  
  Returns:
  
  map of vertex to out-degree centrality | 顶点到出度中心性的映射
- closenessCentrality
  
  public static <V> Map<V,Double> closenessCentrality(Graph<V> graph)
  
  Calculate closeness centrality for all vertices. 计算所有顶点的接近中心性。
  Closeness centrality is the reciprocal of the average shortest path distance to all other vertices. Higher values indicate more central vertices.
  
  接近中心性是到所有其他顶点的平均最短路径距离的倒数。值越高表示顶点越中心。
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the graph | 图
  
  Returns:
  
  map of vertex to closeness centrality | 顶点到接近中心性的映射
- betweennessCentrality
  
  public static <V> Map<V,Double> betweennessCentrality(Graph<V> graph)
  
  Calculate betweenness centrality for all vertices. 计算所有顶点的中介中心性。
  Betweenness centrality measures the number of shortest paths that pass through each vertex. Uses Brandes' algorithm for efficiency.
  
  中介中心性衡量通过每个顶点的最短路径数。使用Brandes算法提高效率。
  
  Time Complexity | 时间复杂度: O(VE)
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the graph | 图
  
  Returns:
  
  map of vertex to betweenness centrality | 顶点到中介中心性的映射
- betweennessCentrality
  
  public static <V> Map<V,Double> betweennessCentrality(Graph<V> graph, boolean normalized)
  
  Calculate betweenness centrality with optional normalization. 计算可选归一化的中介中心性。
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the graph | 图
  
  normalized - whether to normalize results | 是否归一化结果
  
  Returns:
  
  map of vertex to betweenness centrality | 顶点到中介中心性的映射
- pageRank
  
  public static <V> Map<V,Double> pageRank(Graph<V> graph)
  
  Calculate PageRank for all vertices using default parameters. 使用默认参数计算所有顶点的PageRank。
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the graph | 图
  
  Returns:
  
  map of vertex to PageRank score | 顶点到PageRank分数的映射
- pageRank
  
  public static <V> Map<V,Double> pageRank(Graph<V> graph, double dampingFactor, int maxIterations)
  
  Calculate PageRank for all vertices. 计算所有顶点的PageRank。
  PageRank algorithm simulates a random walker on the graph. The damping factor represents the probability of following a link vs. jumping to a random vertex.
  
  PageRank算法模拟图上的随机游走。阻尼因子表示跟随链接与跳转到随机顶点的概率。
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the graph | 图
  
  dampingFactor - damping factor (typically 0.85) | 阻尼因子（通常为0.85）
  
  maxIterations - maximum iterations | 最大迭代次数
  
  Returns:
  
  map of vertex to PageRank score | 顶点到PageRank分数的映射
- pageRank
  
  public static <V> Map<V,Double> pageRank(Graph<V> graph, double dampingFactor, int maxIterations, double tolerance)
  
  Calculate PageRank with convergence tolerance. 带收敛容差计算PageRank。
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the graph | 图
  
  dampingFactor - damping factor (typically 0.85) | 阻尼因子（通常为0.85）
  
  maxIterations - maximum iterations | 最大迭代次数
  
  tolerance - convergence tolerance | 收敛容差
  
  Returns:
  
  map of vertex to PageRank score | 顶点到PageRank分数的映射
- eigenvectorCentrality
  
  public static <V> Map<V,Double> eigenvectorCentrality(Graph<V> graph)
  
  Calculate eigenvector centrality for all vertices. 计算所有顶点的特征向量中心性。
  Eigenvector centrality measures a vertex's importance based on the importance of its neighbors. A vertex with few high-scoring neighbors may have a higher eigenvector centrality than a vertex with many low-scoring neighbors.
  
  特征向量中心性根据邻居的重要性来衡量顶点的重要性。
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the graph | 图
  
  Returns:
  
  map of vertex to eigenvector centrality | 顶点到特征向量中心性的映射
- eigenvectorCentrality
  
  public static <V> Map<V,Double> eigenvectorCentrality(Graph<V> graph, int maxIterations, double tolerance)
  
  Calculate eigenvector centrality with parameters. 带参数计算特征向量中心性。
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the graph | 图
  
  maxIterations - maximum iterations | 最大迭代次数
  
  tolerance - convergence tolerance | 收敛容差
  
  Returns:
  
  map of vertex to eigenvector centrality | 顶点到特征向量中心性的映射
- katzCentrality
  
  public static <V> Map<V,Double> katzCentrality(Graph<V> graph, double alpha, double beta)
  
  Calculate Katz centrality for all vertices. 计算所有顶点的Katz中心性。
  Katz centrality is similar to eigenvector centrality but adds a small constant to prevent nodes with no incoming edges from having zero centrality.
  
  Katz中心性类似于特征向量中心性，但添加一个小常数以防止没有入边的节点具有零中心性。
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the graph | 图
  
  alpha - attenuation factor (should be less than 1/largest eigenvalue) | 衰减因子
  
  beta - base centrality for each node | 每个节点的基础中心性
  
  Returns:
  
  map of vertex to Katz centrality | 顶点到Katz中心性的映射
- katzCentrality
  
  public static <V> Map<V,Double> katzCentrality(Graph<V> graph, double alpha, double beta, int maxIterations, double tolerance)
  
  Calculate Katz centrality with full parameters. 带完整参数计算Katz中心性。
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  graph - the graph | 图
  
  alpha - attenuation factor | 衰减因子
  
  beta - base centrality | 基础中心性
  
  maxIterations - maximum iterations | 最大迭代次数
  
  tolerance - convergence tolerance | 收敛容差
  
  Returns:
  
  map of vertex to Katz centrality | 顶点到Katz中心性的映射
- topK
  
  public static <V> List<V> topK(Map<V,Double> centrality, int k)
  
  Get the top-K most central vertices. 获取前K个最中心的顶点。
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  centrality - the centrality map | 中心性映射
  
  k - the number of top vertices to return | 返回的顶部顶点数
  
  Returns:
  
  list of top-K vertices sorted by centrality | 按中心性排序的前K个顶点列表
- normalize
  
  public static <V> Map<V,Double> normalize(Map<V,Double> centrality)
  
  Normalize centrality values to [0, 1] range. 将中心性值归一化到[0, 1]范围。
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  centrality - the centrality map | 中心性映射
  
  Returns:
  
  normalized centrality map | 归一化的中心性映射
- getStats
  
  public static <V> CentralityUtil.CentralityStats getStats(Map<V,Double> centrality)
  
  Get centrality statistics. 获取中心性统计信息。
  
  Type Parameters:
  
  V - the vertex type | 顶点类型
  
  Parameters:
  
  centrality - the centrality map | 中心性映射
  
  Returns:
  
  centrality statistics | 中心性统计信息

Class CentralityUtil

Nested Class Summary

Field Summary

Method Summary

Methods inherited from class Object

Field Details

DEFAULT_DAMPING_FACTOR

DEFAULT_MAX_ITERATIONS

DEFAULT_TOLERANCE

Method Details

degreeCentrality

inDegreeCentrality

outDegreeCentrality

closenessCentrality

betweennessCentrality

betweennessCentrality

pageRank

pageRank

pageRank

eigenvectorCentrality

eigenvectorCentrality

katzCentrality

katzCentrality

topK

normalize

getStats