java.lang.Object

cloud.opencode.base.graph.algorithm.CommunityDetectionUtil

public final class CommunityDetectionUtil extends Object

Community Detection Util - Graph community detection algorithms 社区检测工具 - 图社区检测算法

Provides algorithms for detecting communities (clusters) in graphs. Communities are groups of vertices that are more densely connected to each other than to vertices in other communities.

提供用于检测图中社区（聚类）的算法。社区是相互之间连接比与其他社区中的顶点连接更紧密的顶点组。

Algorithms | 算法:

Louvain - Fast modularity-based algorithm | 快速模块度优化算法
Label Propagation - Simple iterative algorithm | 简单迭代算法

Features | 主要功能:

Louvain modularity optimization - Louvain模块度优化
Label propagation community detection - 标签传播社区检测
Modularity calculation - 模块度计算
Per-vertex community lookup - 逐顶点社区查询

Usage Examples | 使用示例:

// Detect communities using Louvain algorithm
CommunityResult<String> result = CommunityDetectionUtil.louvain(graph);
List<Set<String>> communities = result.communities();
double modularity = result.modularity();

// Detect communities using Label Propagation
CommunityResult<String> result = CommunityDetectionUtil.labelPropagation(graph);

// Get community for a specific vertex
Set<String> community = CommunityDetectionUtil.getCommunity(result, "A");

// Calculate modularity for given communities
double modularity = CommunityDetectionUtil.calculateModularity(graph, communities);

Security | 安全性:

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

Performance | 性能特性:

Time complexity: O(V log V) for label propagation - 时间复杂度: O(V log V)（标签传播算法）
Space complexity: O(V + E) - 空间复杂度: O(V + E)

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

CommunityDetectionUtil.CommunityResult<V>

Community detection result.
Method Summary

Modifier and Type

Method

Description

static <V> double

calculateModularity(Graph<V> graph, List<Set<V>> communities)

Calculates the modularity score for a given community partition.

static <V> double

calculateModularity(Graph<V> graph, List<Set<V>> communities, double resolution)

Calculates the modularity score with resolution parameter.

static <V> Set<V>

getCommunity(CommunityDetectionUtil.CommunityResult<V> result, V vertex)

Gets the community containing a specific vertex.

static <V> List<Set<V>>

getSortedBySize(CommunityDetectionUtil.CommunityResult<V> result)

Gets communities sorted by size (largest first).

static <V> boolean

inSameCommunity(CommunityDetectionUtil.CommunityResult<V> result, V v1, V v2)

Checks if two vertices are in the same community.

static <V> CommunityDetectionUtil.CommunityResult<V>

labelPropagation(Graph<V> graph)

Detects communities using Label Propagation algorithm.

static <V> CommunityDetectionUtil.CommunityResult<V>

labelPropagation(Graph<V> graph, int maxIterations)

Detects communities using Label Propagation with max iterations.

static <V> CommunityDetectionUtil.CommunityResult<V>

louvain(Graph<V> graph)

Detects communities using the Louvain algorithm.

static <V> CommunityDetectionUtil.CommunityResult<V>

louvain(Graph<V> graph, double resolution, int maxIterations)

Detects communities using the Louvain algorithm with parameters.

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

Method Details
- louvain
  
  public static <V> CommunityDetectionUtil.CommunityResult<V> louvain(Graph<V> graph)
  
  Detects communities using the Louvain algorithm. 使用 Louvain 算法检测社区。
  The Louvain algorithm is a greedy optimization method that attempts to optimize the modularity of a partition.
  
  Louvain 算法是一种贪婪优化方法，尝试优化分区的模块度。
  
  Time Complexity | 时间复杂度: O(n log n) average case
  
  Type Parameters:
  
  V - the vertex type - 顶点类型
  
  Parameters:
  
  graph - the graph - 图
  
  Returns:
  
  the community detection result - 社区检测结果
- louvain
  
  public static <V> CommunityDetectionUtil.CommunityResult<V> louvain(Graph<V> graph, double resolution, int maxIterations)
  
  Detects communities using the Louvain algorithm with parameters. 使用带参数的 Louvain 算法检测社区。
  
  Type Parameters:
  
  V - the vertex type - 顶点类型
  
  Parameters:
  
  graph - the graph - 图
  
  resolution - the resolution parameter (higher = more communities) - 分辨率参数（越高社区越多）
  
  maxIterations - maximum iterations - 最大迭代次数
  
  Returns:
  
  the community detection result - 社区检测结果
- labelPropagation
  
  public static <V> CommunityDetectionUtil.CommunityResult<V> labelPropagation(Graph<V> graph)
  
  Detects communities using Label Propagation algorithm. 使用标签传播算法检测社区。
  A simple and fast algorithm where each vertex adopts the label that most of its neighbors have.
  
  一种简单快速的算法，每个顶点采用其大多数邻居拥有的标签。
  
  Time Complexity | 时间复杂度: O(k * E) where k is iterations
  
  Type Parameters:
  
  V - the vertex type - 顶点类型
  
  Parameters:
  
  graph - the graph - 图
  
  Returns:
  
  the community detection result - 社区检测结果
- labelPropagation
  
  public static <V> CommunityDetectionUtil.CommunityResult<V> labelPropagation(Graph<V> graph, int maxIterations)
  
  Detects communities using Label Propagation with max iterations. 使用带最大迭代次数的标签传播算法检测社区。
  
  Type Parameters:
  
  V - the vertex type - 顶点类型
  
  Parameters:
  
  graph - the graph - 图
  
  maxIterations - maximum iterations - 最大迭代次数
  
  Returns:
  
  the community detection result - 社区检测结果
- calculateModularity
  
  public static <V> double calculateModularity(Graph<V> graph, List<Set<V>> communities)
  
  Calculates the modularity score for a given community partition. 计算给定社区分区的模块度分数。
  Modularity measures the strength of division of a network into communities. Higher values indicate better community structure.
  
  模块度衡量网络划分为社区的强度。较高的值表示更好的社区结构。
  
  Type Parameters:
  
  V - the vertex type - 顶点类型
  
  Parameters:
  
  graph - the graph - 图
  
  communities - the communities - 社区
  
  Returns:
  
  the modularity score [-0.5, 1.0] - 模块度分数
- calculateModularity
  
  public static <V> double calculateModularity(Graph<V> graph, List<Set<V>> communities, double resolution)
  
  Calculates the modularity score with resolution parameter. 使用分辨率参数计算模块度分数。
  
  Type Parameters:
  
  V - the vertex type - 顶点类型
  
  Parameters:
  
  graph - the graph - 图
  
  communities - the communities - 社区
  
  resolution - the resolution parameter - 分辨率参数
  
  Returns:
  
  the modularity score - 模块度分数
- getCommunity
  
  public static <V> Set<V> getCommunity(CommunityDetectionUtil.CommunityResult<V> result, V vertex)
  
  Gets the community containing a specific vertex. 获取包含特定顶点的社区。
  
  Type Parameters:
  
  V - the vertex type - 顶点类型
  
  Parameters:
  
  result - the community result - 社区结果
  
  vertex - the vertex - 顶点
  
  Returns:
  
  the community set or empty set if not found - 社区集合，未找到时返回空集合
- inSameCommunity
  
  public static <V> boolean inSameCommunity(CommunityDetectionUtil.CommunityResult<V> result, V v1, V v2)
  
  Checks if two vertices are in the same community. 检查两个顶点是否在同一社区。
  
  Type Parameters:
  
  V - the vertex type - 顶点类型
  
  Parameters:
  
  result - the community result - 社区结果
  
  v1 - first vertex - 第一个顶点
  
  v2 - second vertex - 第二个顶点
  
  Returns:
  
  true if same community - 如果在同一社区返回 true
- getSortedBySize
  
  public static <V> List<Set<V>> getSortedBySize(CommunityDetectionUtil.CommunityResult<V> result)
  
  Gets communities sorted by size (largest first). 获取按大小排序的社区（最大优先）。
  
  Type Parameters:
  
  V - the vertex type - 顶点类型
  
  Parameters:
  
  result - the community result - 社区结果
  
  Returns:
  
  sorted list of communities - 排序后的社区列表

Class CommunityDetectionUtil

Nested Class Summary

Method Summary

Methods inherited from class Object

Method Details

louvain

louvain

labelPropagation

labelPropagation

calculateModularity

calculateModularity

getCommunity

inSameCommunity

getSortedBySize