"""
Hyperbolic Embeddings for ExpoComm
Implements hyperbolic space embeddings (Poincaré disk) for graphs,
enabling O(log N) greedy routing and exponential scaling.
"""
module HyperbolicEmbeddingsModule
export PoincareDisk, hyperbolic_distance, hyperbolic_embedding
export greedy_route, reflect_point, geodesic
using LinearAlgebra
using Random
using Statistics
"""
Point in Poincaré disk model of hyperbolic space
"""
struct PoincarePoint
coords::Vector{Float64} # Must satisfy ||coords|| < 1
function PoincarePoint(coords::Vector{Float64})
norm_sq = sum(coords .^ 2)
@assert norm_sq < 1.0 "Point must be inside unit disk"
new(coords)
end
end
# Origin of Poincaré disk
origin() = PoincarePoint(zeros(2))
"""
Hyperbolic distance in Poincaré disk
d(x, y) = acosh(1 + 2||x - y||²/((1 - ||x||²)(1 - ||y||²)))
"""
function hyperbolic_distance(p::PoincarePoint, q::PoincarePoint)
x = p.coords
y = q.coords
norm_x_sq = sum(x .^ 2)
norm_y_sq = sum(y .^ 2)
norm_diff_sq = sum((x - y) .^ 2)
numerator = 2 * norm_diff_sq
denominator = (1 - norm_x_sq) * (1 - norm_y_sq)
# Avoid numerical issues
arg = 1 + numerator / max(denominator, 1e-10)
return acosh(max(arg, 1.0))
end
"""
Reflect point through hyperbolic geodesic (Möbius transformation)
"""
function reflect_point(p::PoincarePoint, through::PoincarePoint)
# Simplified reflection (full implementation requires Möbius transformations)
# This is a placeholder
return p
end
"""
Hyperbolic midpoint
"""
function hyperbolic_midpoint(p::PoincarePoint, q::PoincarePoint)
# Approximate via Euclidean midpoint and projection
mid = (p.coords + q.coords) / 2
# Project back to valid radius
norm_sq = sum(mid .^ 2)
if norm_sq >= 1.0
mid = mid * 0.99 / sqrt(norm_sq)
end
return PoincarePoint(mid)
end
"""
Hyperbolic embedding via force-directed layout
"""
function hyperbolic_embedding(adjacency_matrix::Matrix{Float64};
dim::Int=2,
iterations::Int=500,
learning_rate::Float64=0.01)
N = size(adjacency_matrix, 1)
# Initialize random points in disk
embeddings = [PoincarePoint(randn(dim) * 0.1) for _ in 1:N]
for iter in 1:iterations
# Compute forces
for i in 1:N
force = zeros(dim)
for j in 1:N
if i != j
d = hyperbolic_distance(embeddings[i], embeddings[j])
# Attractive force for connected nodes
if adjacency_matrix[i, j] > 0
# Pull together
direction = embeddings[j].coords - embeddings[i].coords
force += direction * adjacency_matrix[i, j] * 0.1
else
# Repulsive force for non-connected nodes
direction = embeddings[i].coords - embeddings[j].coords
force += direction / max(d^2, 0.01) * 0.01
end
end
end
# Update position
new_coords = embeddings[i].coords + learning_rate * force
# Project to disk
norm_sq = sum(new_coords .^ 2)
if norm_sq >= 1.0
new_coords = new_coords * 0.99 / sqrt(norm_sq)
end
embeddings[i] = PoincarePoint(new_coords)
end
end
return embeddings
end
"""
Greedy routing in hyperbolic space
"""
function greedy_route(embeddings::Vector{PoincarePoint},
adjacency_matrix::Matrix{Float64},
source::Int,
target::Int)
N = length(embeddings)
current = source
path = [current]
visited = Set([current])
max_hops = Int(ceil(2 * log2(N))) # O(log N) guarantee
for hop in 1:max_hops
if current == target
return path
end
# Find neighbor closest to target in hyperbolic space
neighbors = findall(adjacency_matrix[current, :] .> 0)
if isempty(neighbors)
# Dead end
return path
end
# Greedy choice: neighbor with minimum hyperbolic distance to target
distances = [hyperbolic_distance(embeddings[n], embeddings[target]) for n in neighbors]
best_neighbor_idx = argmin(distances)
next_node = neighbors[best_neighbor_idx]
if next_node in visited
# Cycle detected, break
break
end
push!(visited, next_node)
push!(path, next_node)
current = next_node
end
return path
end
"""
Compute average path length for greedy routing
"""
function average_greedy_path_length(embeddings::Vector{PoincarePoint},
adjacency_matrix::Matrix{Float64},
n_samples::Int=100)
N = length(embeddings)
path_lengths = Float64[]
for _ in 1:n_samples
source = rand(1:N)
target = rand(1:N)
if source != target
path = greedy_route(embeddings, adjacency_matrix, source, target)
# Check if reached target
if path[end] == target
push!(path_lengths, length(path) - 1) # Number of hops
end
end
end
if isempty(path_lengths)
return Inf
end
return mean(path_lengths)
end
"""
Compute embedding quality metric
"""
function embedding_quality(embeddings::Vector{PoincarePoint},
adjacency_matrix::Matrix{Float64})
N = length(embeddings)
# Distortion: ratio of hyperbolic to graph distances
graph_distances = floyd_warshall(adjacency_matrix)
distortions = Float64[]
for i in 1:N
for j in (i+1):N
h_dist = hyperbolic_distance(embeddings[i], embeddings[j])
g_dist = graph_distances[i, j]
if isfinite(g_dist) && g_dist > 0
distortion = h_dist / g_dist
push!(distortions, distortion)
end
end
end
return (
mean_distortion=mean(distortions),
std_distortion=std(distortions)
)
end
"""
Floyd-Warshall all-pairs shortest paths (placeholder)
"""
function floyd_warshall(adjacency::Matrix{Float64})
N = size(adjacency, 1)
dist = fill(Inf, N, N)
# Initialize
for i in 1:N
dist[i, i] = 0.0
for j in 1:N
if adjacency[i, j] > 0
dist[i, j] = 1.0
end
end
end
# Floyd-Warshall
for k in 1:N
for i in 1:N
for j in 1:N
dist[i, j] = min(dist[i, j], dist[i, k] + dist[k, j])
end
end
end
return dist
end
end # module