NGF_on_Fractale / src /modules /tab_b0_clusters.py
antaris's picture
Upload 33 files
5543795 verified
Raw History Blame Contribute Delete
18.7 kB
from __future__ import annotations
from typing import Dict, List, Sequence, Tuple
import networkx as nx
import numpy as np
import plotly.graph_objects as go
import streamlit as st
from . import dimension_utils
TAB_TITLE = "B.0 – Clusteranalyse"
TAB_ORDER = 50
def _compute_typical_edge_length(G: nx.Graph, coords: Dict[int, np.ndarray]) -> float:
"""Bestimme eine typische Kantenlänge (Median) aus der Einbettung.
Falls keine Kanten oder unvollständige Koordinaten vorhanden sind,
wird 1.0 als Fallback verwendet.
"""
edge_lengths: List[float] = []
for u, v in G.edges:
if u not in coords or v not in coords:
continue
ru = np.asarray(coords[u], dtype=float)
rv = np.asarray(coords[v], dtype=float)
edge_lengths.append(float(np.linalg.norm(rv - ru)))
if edge_lengths:
return float(np.median(edge_lengths))
return 1.0
def _auto_cluster_params(
G: nx.Graph,
coords: Dict[int, np.ndarray],
ell_edge: float,
) -> Dict[str, float]:
"""Heuristische Auto-Setup-Funktion für die Cluster-/Patchanalyse.
Leitet sinnvolle Startwerte für die Regler aus den verfügbaren Daten ab:
- Anzahl Knoten/Kanten
- typische Kantenlänge ℓ_edge
- mittlere Knotengrade
Die Werte werden nur als *Vorschläge* verwendet; der Nutzer kann sie
über die Regler jederzeit überschreiben.
"""
n_nodes = G.number_of_nodes()
n_edges = G.number_of_edges()
n_nodes = max(n_nodes, 1)
# mittlerer Knotengrad
avg_deg = 2.0 * n_edges / n_nodes if n_nodes > 0 else 0.0
# Radius in Einheiten von ℓ_edge:
# - kleinere Graphen: eher etwas größerer Radius, um genügend Nachbarn zu haben
# - dichte/hochgradige Graphen: Radius leicht reduzieren
if n_nodes < 500:
R_units = 2.0
elif n_nodes < 2000:
R_units = 2.5
elif n_nodes < 10000:
R_units = 3.0
else:
R_units = 3.5
if avg_deg > 6:
R_units *= 0.9
elif avg_deg < 3:
R_units *= 1.1
# Begrenzung auf Sliderbereich
R_units = float(np.clip(R_units, 0.5, 5.0))
# Dichteschwelle:
# - kleine Graphen: niedrigeres Perzentil, um genügend Knoten zu bekommen
# - große Graphen: höheres Perzentil, um nur die wirklich dichten Regionen zu nehmen
if n_nodes < 500:
percentile = 70
elif n_nodes < 2000:
percentile = 80
elif n_nodes < 10000:
percentile = 90
else:
percentile = 95
# minimale Clustergröße:
# skalieren mit N, aber begrenzen nach oben/unten
min_cluster_size = max(5, n_nodes // 200)
max_reasonable = max(10, n_nodes // 20)
if min_cluster_size > max_reasonable:
min_cluster_size = max_reasonable
# Radius-Schritte für die Dimensionsanalyse
if n_nodes < 500:
max_r_steps = 5
elif n_nodes < 2000:
max_r_steps = 6
elif n_nodes < 10000:
max_r_steps = 7
else:
max_r_steps = 8
# Seeds pro Cluster für die Dimensionsanalyse
if n_nodes < 500:
seeds_per_cluster = 2
elif n_nodes < 2000:
seeds_per_cluster = 3
else:
seeds_per_cluster = 4
return {
"R_units": float(R_units),
"percentile": float(percentile),
"min_cluster_size": float(min_cluster_size),
"max_r_steps": float(max_r_steps),
"seeds_per_cluster": float(seeds_per_cluster),
}
def _compute_local_densities(
coords: Dict[int, np.ndarray],
radius: float,
) -> Tuple[List[int], np.ndarray]:
"""Berechne lokale Knotendichten für einen gegebenen geometrischen Radius.
Für jeden Knoten i wird die Anzahl der Knoten innerhalb des Radius R
gezählt:
rho_R(i) = |{ j : ||r_j - r_i|| <= R }|
Rückgabe:
nodes: Liste der Knoten-IDs in derselben Reihenfolge wie rho
rho: Array der Dichten (gleiche Länge wie nodes)
"""
if not coords:
return [], np.zeros(0, dtype=float)
nodes = list(coords.keys())
pos_arr = np.stack([np.asarray(coords[n], dtype=float) for n in nodes], axis=0)
n = pos_arr.shape[0]
rho = np.zeros(n, dtype=float)
# O(N^2)-Algorithmus, aber mit NumPy-Vektorisierung ausreichend schnell
for i in range(n):
di = np.linalg.norm(pos_arr - pos_arr[i], axis=1)
rho[i] = float((di <= float(radius)).sum())
return nodes, rho
def _detect_clusters(
G: nx.Graph,
nodes: Sequence[int],
densities: np.ndarray,
percentile: float,
min_cluster_size: int,
) -> Tuple[List[List[int]], float]:
"""Finde Cluster als zusammenhängende Komponenten hochdichter Knoten.
- Die Dichte-Schwelle wird als Perzentil über rho bestimmt.
- Es wird der induzierte Teilgraph der Knoten mit rho >= Schwelle gebildet.
- Zusammenhängende Komponenten mit Größe >= min_cluster_size gelten als Cluster.
Rückgabe:
clusters: Liste von Listen von Knoten-IDs (nach absteigender Größe sortiert)
rho_th: verwendete Dichte-Schwelle
"""
if len(nodes) == 0 or densities.size == 0:
return [], float("nan")
rho_th = float(np.percentile(densities, percentile))
selected = [n for n, r in zip(nodes, densities) if r >= rho_th]
if not selected:
return [], rho_th
H = G.subgraph(selected).copy()
comps = [
sorted(list(c))
for c in nx.connected_components(H)
if len(c) >= min_cluster_size
]
# Größte Cluster zuerst
comps.sort(key=len, reverse=True)
return comps, rho_th
def _estimate_cluster_dimension(
G: nx.Graph,
coords: Dict[int, np.ndarray],
cluster_nodes: Sequence[int],
max_r_steps: int,
num_seeds: int,
rng: np.random.Generator,
) -> Tuple[float, float]:
"""Schätze die geometrische Dimension eines Clusters.
- Es wird ein Teilgraph auf cluster_nodes gebildet.
- Seeds werden zufällig aus dem Cluster gewählt.
- Es wird compute_ball_growth_geometric auf diesem Teilgraphen verwendet.
- Aus N_x(R) wird mittels estimate_dimension_from_counts die Dimension bestimmt.
Rückgabe:
(d_mean, d_std) – Mittelwert und Streuung über Seeds.
Falls keine sinnvolle Schätzung möglich ist, werden (nan, nan) zurückgegeben.
"""
if len(cluster_nodes) < 2:
return float("nan"), float("nan")
subG = G.subgraph(cluster_nodes).copy()
sub_coords = {n: coords[n] for n in cluster_nodes if n in coords}
if len(sub_coords) < 2:
return float("nan"), float("nan")
available_nodes = list(sub_coords.keys())
n_seeds = min(max(1, num_seeds), len(available_nodes))
seeds = rng.choice(available_nodes, size=n_seeds, replace=False)
r_vals, counts = dimension_utils.compute_ball_growth_geometric(
subG,
sub_coords,
seeds,
r_max_steps=max_r_steps,
)
if r_vals.size == 0 or counts.size == 0:
return float("nan"), float("nan")
# Fit-Bereich: interne Radien (wenn möglich) verwenden
if len(r_vals) >= 3:
r_min_fit = float(r_vals[1])
r_max_fit = float(r_vals[-1])
else:
r_min_fit = float(r_vals[0])
r_max_fit = float(r_vals[-1])
dims = []
for k in range(counts.shape[0]):
d_k = dimension_utils.estimate_dimension_from_counts(
r_vals,
counts[k, :],
r_min_fit=r_min_fit,
r_max_fit=r_max_fit,
)
dims.append(d_k)
d_arr = np.asarray(dims, dtype=float)
if np.all(np.isnan(d_arr)):
return float("nan"), float("nan")
return float(np.nanmean(d_arr)), float(np.nanstd(d_arr))
def render_tab(context: Dict):
st.subheader("Lokale Cluster- und Patchanalyse")
fractal_id = context["fractal_id"]
level = context["level"]
G_ideal = context["G_ideal"]
pos_ideal = context["pos_ideal"]
G_real = context["G_real"]
pos_real = context["pos_real"]
boundary_nodes = context["boundary_nodes"]
seed_global = int(context.get("random_seed", 42))
st.markdown(
f"""
**Fraktal:** `{fractal_id}` &nbsp;&nbsp; **Level:** `{level}`
**Knoten (IDEAL):** {G_ideal.number_of_nodes()} &nbsp;&nbsp; **Kanten (IDEAL):** {G_ideal.number_of_edges()}
Dieses Tab analysiert lokale Dichtefluktuationen in der eingebetteten Struktur
und identifiziert hochdichte Cluster/Patches im Graphen.
"""
)
with st.expander("Einstellungen für die Cluster- und Patchanalyse", expanded=True):
graph_choice = st.radio(
"Graph für die Clusteranalyse",
("REAL-Graph (empfohlen)", "IDEAL-Graph"),
index=0,
help=(
"Beim REAL-Graph sind Kantengewichte und Geometrie bereits durch Bad und Selbstwechselwirkung "
"verändert. Der IDEAL-Graph dient als Referenz."
),
)
if graph_choice.startswith("REAL"):
G = G_real
coords = pos_real
else:
G = G_ideal
coords = pos_ideal
ell_edge = _compute_typical_edge_length(G, coords)
st.markdown(
f"Typische Kantenlänge (Median) in der Einbettung: **ℓ_edge ≈ {ell_edge:.3g}**"
)
# Auto-Setup: heuristische Vorschläge für alle relevanten Parameter
auto_params = _auto_cluster_params(G, coords, ell_edge)
st.markdown(
"Die initialen Werte der Regler werden automatisch aus den Graphparametern "
"(Anzahl Knoten/Kanten, mittlerer Grad, ℓ_edge) abgeleitet und können bei Bedarf manuell angepasst werden."
)
# Radius R (in Einheiten von ℓ_edge)
R_units_default = float(np.clip(auto_params["R_units"], 0.5, 5.0))
R_units = st.slider(
"Radius R für lokale Dichte (in Einheiten von ℓ_edge)",
min_value=0.5,
max_value=5.0,
value=R_units_default,
step=0.5,
help=(
"R bestimmt den lokalen Nachbarschaftsbereich: "
"Für jeden Knoten werden alle Knoten innerhalb Distanz R·ℓ_edge gezählt."
),
)
R = float(R_units * ell_edge)
# Dichteschwelle (Perzentil)
percentile_default = int(np.clip(auto_params["percentile"], 50, 99))
percentile = st.slider(
"Dichteschwelle (Perzentil)",
min_value=50,
max_value=99,
value=percentile_default,
step=1,
help=(
"Knoten mit einer Dichte oberhalb dieses Perzentils werden als hochdicht betrachtet "
"und für die Clusterbildung verwendet."
),
)
max_nodes = G.number_of_nodes()
# Sliderbereich dynamisch, Default aus Auto-Setup, aber auf Bereich begrenzt
min_cluster_size_min = 5
min_cluster_size_max = max(10, max_nodes // 5) if max_nodes > 0 else 10
min_cluster_size_default = int(
np.clip(auto_params["min_cluster_size"], min_cluster_size_min, min_cluster_size_max)
)
min_cluster_size = st.slider(
"Minimale Clustergröße (Anzahl Knoten)",
min_value=min_cluster_size_min,
max_value=min_cluster_size_max,
value=min_cluster_size_default,
step=5,
help="Zusammenhängende Komponenten kleiner als diese Größe werden verworfen.",
)
# max. Radius-Schritte für Dimensionsanalyse
max_r_steps_default = int(np.clip(auto_params["max_r_steps"], 3, 10))
max_r_steps = st.slider(
"Maximaler Radius (Schritte) für Dimensionsanalyse pro Cluster",
min_value=3,
max_value=10,
value=max_r_steps_default,
step=1,
)
# Seeds pro Cluster
seeds_default = int(np.clip(auto_params["seeds_per_cluster"], 1, 6))
seeds_per_cluster = st.slider(
"Anzahl Seeds pro Cluster für Dimensionsanalyse",
min_value=1,
max_value=6,
value=seeds_default,
step=1,
)
st.markdown(
"Hinweis: Die Berechnung der lokalen Dichte ist O(N²) und kann bei großen Graphen einige Sekunden dauern."
)
rng = np.random.default_rng(seed_global + 17)
with st.spinner("Berechne lokale Dichten und Cluster ..."):
nodes, rho = _compute_local_densities(coords, radius=R)
if len(nodes) == 0:
st.warning("Keine Koordinaten verfügbar – Clusteranalyse nicht möglich.")
return
clusters, rho_th = _detect_clusters(
G,
nodes,
rho,
percentile=float(percentile),
min_cluster_size=int(min_cluster_size),
)
st.markdown(
f"Verwendete Dichteschwelle: **ρ_th = {rho_th:.1f}** "
f"(Perzentil {percentile} der lokalen Dichten)."
)
if not clusters:
st.info(
"Mit den aktuellen Parametern wurden keine Cluster mit ausreichender Größe gefunden. "
"Reduziere die Dichteschwelle oder die minimale Clustergröße."
)
return
# Robuste Behandlung: kein Slider, wenn genau ein Cluster gefunden wurde
n_clusters = len(clusters)
if n_clusters == 1:
st.info(
"Mit den aktuellen Parametern wurde genau ein Cluster gefunden. "
"Die Analyse wird für diesen einen Cluster durchgeführt."
)
max_clusters = 1
else:
max_clusters = st.slider(
"Maximale Anzahl ausgewerteter Cluster (nach Größe)",
min_value=1,
max_value=min(6, n_clusters),
value=min(3, n_clusters),
step=1,
)
# Dimensionsanalyse pro Cluster
cluster_summaries = []
for idx, cluster_nodes in enumerate(clusters[:max_clusters]):
d_mean, d_std = _estimate_cluster_dimension(
G,
coords,
cluster_nodes,
max_r_steps=max_r_steps,
num_seeds=seeds_per_cluster,
rng=rng,
)
dens_values = [rho[nodes.index(n)] for n in cluster_nodes if n in nodes]
avg_dens = float(np.mean(dens_values)) if dens_values else float("nan")
cluster_summaries.append(
{
"Cluster": idx + 1,
"Knoten": len(cluster_nodes),
"⟨ρ_R⟩": avg_dens,
"d_eff": d_mean,
"σ_d": d_std,
}
)
st.markdown("### Zusammenfassung der größten Cluster")
try:
import pandas as pd # type: ignore
df = pd.DataFrame(cluster_summaries)
st.dataframe(df, use_container_width=True)
except Exception:
# Fallback ohne pandas
for cs in cluster_summaries:
st.markdown(
f"- **Cluster {cs['Cluster']}**: "
f"{cs['Knoten']} Knoten, ⟨ρ_R⟩ ≈ {cs['⟨ρ_R⟩']:.1f}, "
f"d_eff ≈ {cs['d_eff']:.3f} ± {cs['σ_d']:.3f}"
)
# Visualisierung: Cluster farblich markieren
st.markdown("### Geometrische Struktur der Cluster")
show_edges = st.checkbox(
"Kanten im Plot anzeigen",
value=False,
help="Zur besseren Übersicht können die Kanten ausgeblendet werden.",
)
# Farbschema für Cluster (begrenzte Palette, wird bei Bedarf zyklisch wiederverwendet)
color_cycle = [
"#e41a1c",
"#377eb8",
"#4daf4a",
"#984ea3",
"#ff7f00",
"#ffff33",
"#a65628",
"#f781bf",
]
cluster_id_by_node = {}
for idx, cluster_nodes in enumerate(clusters[:max_clusters]):
for n in cluster_nodes:
cluster_id_by_node[n] = idx
x_bg = []
y_bg = []
z_bg = []
for n in nodes:
if n in cluster_id_by_node:
continue
p = coords[n]
x_bg.append(p[0])
y_bg.append(p[1])
z_bg.append(p[2])
fig = go.Figure()
if show_edges:
x_e = []
y_e = []
z_e = []
for u, v in G.edges:
if u not in coords or v not in coords:
continue
p0 = coords[u]
p1 = coords[v]
x_e += [p0[0], p1[0], None]
y_e += [p0[1], p1[1], None]
z_e += [p0[2], p1[2], None]
fig.add_trace(
go.Scatter3d(
x=x_e,
y=y_e,
z=z_e,
mode="lines",
name="Kanten",
line=dict(width=1, color="rgba(150,150,200,0.35)"),
hoverinfo="skip",
)
)
# Hintergrundknoten (nicht im Cluster)
fig.add_trace(
go.Scatter3d(
x=x_bg,
y=y_bg,
z=z_bg,
mode="markers",
name="Hintergrund",
marker=dict(size=2, color="rgba(180,180,180,0.4)"),
hoverinfo="skip",
)
)
# Clusterknoten
for idx, cluster_nodes in enumerate(clusters[:max_clusters]):
xs = []
ys = []
zs = []
for n in cluster_nodes:
if n not in coords:
continue
p = coords[n]
xs.append(p[0])
ys.append(p[1])
zs.append(p[2])
color = color_cycle[idx % len(color_cycle)]
fig.add_trace(
go.Scatter3d(
x=xs,
y=ys,
z=zs,
mode="markers",
name=f"Cluster {idx + 1}",
marker=dict(size=4, color=color),
hoverinfo="text",
text=[f"Cluster {idx + 1}, Node {n}" for n in cluster_nodes],
)
)
# Randknoten (zur Orientierung)
x_bd = []
y_bd = []
z_bd = []
for b in boundary_nodes:
if b not in coords:
continue
p = coords[b]
x_bd.append(p[0])
y_bd.append(p[1])
z_bd.append(p[2])
if x_bd:
fig.add_trace(
go.Scatter3d(
x=x_bd,
y=y_bd,
z=z_bd,
mode="markers",
name="Randknoten",
marker=dict(size=3, color="black", symbol="diamond"),
hoverinfo="skip",
)
)
fig.update_layout(
scene=dict(
xaxis_title="x",
yaxis_title="y",
zaxis_title="z",
aspectmode="data",
),
legend=dict(orientation="h", yanchor="bottom", y=1.02, xanchor="left", x=0.0),
margin=dict(l=0, r=0, b=0, t=30),
)
st.plotly_chart(fig, use_container_width=True)