metrics

Metrics for evaluating community structure and topological properties.

Provides various metrics to measure the quality of detected communities and analyze graph topology including modularity, clustering coefficients, and triangle counts.

Metrics

Metric	Function	Use Case
Modularity	`modularity/2`	Quality of community partition
Triangle Count	`count_triangles/1`	Global clustering measure
Local Clustering	`clustering_coefficient/2`	Node-level clustering
Global Clustering	`average_clustering_coefficient/1`	Graph-wide clustering
Density	`density/1`	Edge density of graph
Community Density	`community_density/2`	Internal edge density

Modularity

Modularity Q measures the density of edges inside communities compared to what would be expected by chance. Ranges from -1 to 1, with positive values indicating community structure better than random.

Example

import yog
import yog/community/louvain
import yog/community/metrics

let graph = // ... build graph

// Detect communities and evaluate
let communities = louvain.detect(graph)
let q = metrics.modularity(graph, communities)
// q > 0.3 generally indicates good community structure

// Graph topology metrics
let triangles = metrics.count_triangles(graph)
let avg_clustering = metrics.average_clustering_coefficient(graph)
let graph_density = metrics.density(graph)

// Community-specific metrics
let community_dict = community.communities_to_dict(communities)
let first_comm = case dict.get(community_dict, 0) {
  Ok(nodes) -> metrics.community_density(graph, nodes)
  Error(Nil) -> 0.0
}

Values

average_clustering_coefficient

</>

pub fn average_clustering_coefficient(
  graph: model.Graph(n, e),
) -> Float

Calculates the average clustering coefficient for the entire graph.

average_community_density

</>

pub fn average_community_density(
  graph: model.Graph(n, e),
  communities: community.Communities,
) -> Float

Average density across all communities.

clustering_coefficient

</>

pub fn clustering_coefficient(
  graph: model.Graph(n, e),
  node: Int,
) -> Float

Calculates the local clustering coefficient for a node.

community_density

</>

pub fn community_density(
  graph: model.Graph(n, e),
  community: set.Set(Int),
) -> Float

Density within a community (ratio of internal edges to possible edges).

count_triangles

</>

pub fn count_triangles(graph: model.Graph(n, e)) -> Int

Count total triangles in the graph. A triangle is a set of three nodes where all are connected.

Time Complexity: O(V * k^2) where k is average degree.

density

</>

pub fn density(graph: model.Graph(n, e)) -> Float

Graph density: ratio of actual edges to maximum possible edges.

modularity

</>

pub fn modularity(
  graph: model.Graph(n, Int),
  communities: community.Communities,
) -> Float

Calculates Newman’s modularity Q for an undirected graph.

Q measures the density of edges inside communities compared to what would be expected by chance.

Time Complexity: O(E)

triangles_per_node

</>

pub fn triangles_per_node(
  graph: model.Graph(n, e),
) -> dict.Dict(Int, Int)

Returns a dictionary mapping each node to the number of triangles it participates in.