|
1
|
""" |
|
2
|
CommunityDetector — label propagation community detection over the navegador graph. |
|
3
|
|
|
4
|
Implements a simple synchronous label-propagation algorithm: |
|
5
|
1. Each node starts as its own community (label = node id). |
|
6
|
2. On each iteration every node adopts the most common label among its |
|
7
|
neighbours (ties broken by lowest label value). |
|
8
|
3. Repeat until stable or ``max_iter`` reached. |
|
9
|
4. Collect nodes sharing the same label into ``Community`` objects. |
|
10
|
|
|
11
|
Usage:: |
|
12
|
|
|
13
|
from navegador.graph import GraphStore |
|
14
|
from navegador.intelligence.community import CommunityDetector |
|
15
|
|
|
16
|
store = GraphStore.sqlite(".navegador/graph.db") |
|
17
|
detector = CommunityDetector(store) |
|
18
|
communities = detector.detect(min_size=2) |
|
19
|
detector.store_communities() |
|
20
|
""" |
|
21
|
|
|
22
|
from __future__ import annotations |
|
23
|
|
|
24
|
from collections import Counter |
|
25
|
from dataclasses import dataclass, field |
|
26
|
from typing import TYPE_CHECKING, Any |
|
27
|
|
|
28
|
if TYPE_CHECKING: |
|
29
|
from navegador.graph.store import GraphStore |
|
30
|
|
|
31
|
|
|
32
|
# ── Cypher helpers ──────────────────────────────────────────────────────────── |
|
33
|
|
|
34
|
# Fetch all node ids and names (we use the internal FalkorDB node id via id(n)) |
|
35
|
_ALL_NODES = """ |
|
36
|
MATCH (n) |
|
37
|
WHERE n.name IS NOT NULL |
|
38
|
RETURN id(n) AS id, n.name AS name, |
|
39
|
coalesce(n.file_path, '') AS file_path, |
|
40
|
labels(n)[0] AS type |
|
41
|
""" |
|
42
|
|
|
43
|
# Fetch all edges as (from_id, to_id) — undirected for community purposes |
|
44
|
_ALL_EDGES = """ |
|
45
|
MATCH (a)-[r]->(b) |
|
46
|
WHERE a.name IS NOT NULL AND b.name IS NOT NULL |
|
47
|
RETURN id(a) AS src, id(b) AS dst |
|
48
|
""" |
|
49
|
|
|
50
|
# Write the community label back onto a node |
|
51
|
_SET_COMMUNITY = """ |
|
52
|
MATCH (n) |
|
53
|
WHERE id(n) = $node_id |
|
54
|
SET n.community = $community |
|
55
|
""" |
|
56
|
|
|
57
|
|
|
58
|
# ── Data model ──────────────────────────────────────────────────────────────── |
|
59
|
|
|
60
|
|
|
61
|
@dataclass |
|
62
|
class Community: |
|
63
|
"""A detected community in the graph. |
|
64
|
|
|
65
|
Attributes: |
|
66
|
name: Auto-generated name (e.g. ``"community_3"``). Can be replaced |
|
67
|
by :class:`~navegador.intelligence.nlp.NLPEngine.name_communities`. |
|
68
|
members: Node names belonging to this community. |
|
69
|
size: ``len(members)``. |
|
70
|
density: Fraction of possible internal edges that actually exist |
|
71
|
(0.0–1.0). Computed lazily; ``-1.0`` means not yet calculated. |
|
72
|
""" |
|
73
|
|
|
74
|
name: str |
|
75
|
members: list[str] = field(default_factory=list) |
|
76
|
size: int = 0 |
|
77
|
density: float = -1.0 |
|
78
|
|
|
79
|
def __post_init__(self) -> None: |
|
80
|
if self.size == 0: |
|
81
|
self.size = len(self.members) |
|
82
|
|
|
83
|
|
|
84
|
# ── Detector ───────────────────────────────────────────────────────────────── |
|
85
|
|
|
86
|
|
|
87
|
class CommunityDetector: |
|
88
|
""" |
|
89
|
Detect communities in the navegador graph via label propagation. |
|
90
|
|
|
91
|
Args: |
|
92
|
store: A :class:`~navegador.graph.GraphStore` instance. |
|
93
|
""" |
|
94
|
|
|
95
|
def __init__(self, store: "GraphStore") -> None: |
|
96
|
self._store = store |
|
97
|
# Populated after detect() |
|
98
|
self._communities: list[Community] = [] |
|
99
|
# id -> label mapping after propagation |
|
100
|
self._labels: dict[int, int] = {} |
|
101
|
# id -> name/meta mapping |
|
102
|
self._nodes: dict[int, dict[str, Any]] = {} |
|
103
|
|
|
104
|
# ── Public API ──────────────────────────────────────────────────────────── |
|
105
|
|
|
106
|
def detect(self, min_size: int = 2, max_iter: int = 50) -> list[Community]: |
|
107
|
""" |
|
108
|
Run label-propagation and return communities with at least *min_size* |
|
109
|
members. |
|
110
|
|
|
111
|
Args: |
|
112
|
min_size: Minimum community size to include in results. |
|
113
|
max_iter: Maximum number of propagation iterations. |
|
114
|
|
|
115
|
Returns: |
|
116
|
List of :class:`Community` objects, sorted largest-first. |
|
117
|
""" |
|
118
|
nodes, edges = self._load_graph() |
|
119
|
if not nodes: |
|
120
|
self._communities = [] |
|
121
|
return [] |
|
122
|
|
|
123
|
# Initialise: each node is its own community |
|
124
|
labels: dict[int, int] = {nid: nid for nid in nodes} |
|
125
|
|
|
126
|
# Build adjacency list (undirected) |
|
127
|
adj: dict[int, list[int]] = {nid: [] for nid in nodes} |
|
128
|
for src, dst in edges: |
|
129
|
if src in adj and dst in adj: |
|
130
|
adj[src].append(dst) |
|
131
|
adj[dst].append(src) |
|
132
|
|
|
133
|
# Propagation loop |
|
134
|
for _ in range(max_iter): |
|
135
|
changed = False |
|
136
|
for nid in sorted(nodes): # deterministic order |
|
137
|
neighbours = adj[nid] |
|
138
|
if not neighbours: |
|
139
|
continue |
|
140
|
counts: Counter = Counter(labels[nb] for nb in neighbours if nb in labels) |
|
141
|
if not counts: |
|
142
|
continue |
|
143
|
best_label = min(counts, key=lambda lbl: (-counts[lbl], lbl)) |
|
144
|
if best_label != labels[nid]: |
|
145
|
labels[nid] = best_label |
|
146
|
changed = True |
|
147
|
if not changed: |
|
148
|
break |
|
149
|
|
|
150
|
self._labels = labels |
|
151
|
self._nodes = nodes |
|
152
|
self._communities = self._build_communities(labels, nodes, adj, min_size) |
|
153
|
return self._communities |
|
154
|
|
|
155
|
def store_communities(self) -> int: |
|
156
|
""" |
|
157
|
Write community labels as a ``community`` property on all nodes. |
|
158
|
|
|
159
|
Must call :meth:`detect` first. |
|
160
|
|
|
161
|
Returns: |
|
162
|
Number of nodes updated. |
|
163
|
""" |
|
164
|
updated = 0 |
|
165
|
for node_id, label in self._labels.items(): |
|
166
|
# Find community name for this label |
|
167
|
comm_name = f"community_{label}" |
|
168
|
for c in self._communities: |
|
169
|
if c.name == comm_name: |
|
170
|
break |
|
171
|
# Use numeric label as community identifier |
|
172
|
self._store.query(_SET_COMMUNITY, {"node_id": node_id, "community": label}) |
|
173
|
updated += 1 |
|
174
|
return updated |
|
175
|
|
|
176
|
# ── Internals ───────────────────────────────────────────────────────────── |
|
177
|
|
|
178
|
def _load_graph( |
|
179
|
self, |
|
180
|
) -> tuple[dict[int, dict[str, Any]], list[tuple[int, int]]]: |
|
181
|
"""Load all nodes and edges from the store.""" |
|
182
|
node_result = self._store.query(_ALL_NODES, {}) |
|
183
|
nodes: dict[int, dict[str, Any]] = {} |
|
184
|
for row in node_result.result_set or []: |
|
185
|
nid, name, file_path, node_type = row[0], row[1], row[2], row[3] |
|
186
|
nodes[nid] = {"name": name, "file_path": file_path, "type": node_type} |
|
187
|
|
|
188
|
edge_result = self._store.query(_ALL_EDGES, {}) |
|
189
|
edges: list[tuple[int, int]] = [] |
|
190
|
for row in edge_result.result_set or []: |
|
191
|
src, dst = row[0], row[1] |
|
192
|
edges.append((src, dst)) |
|
193
|
|
|
194
|
return nodes, edges |
|
195
|
|
|
196
|
@staticmethod |
|
197
|
def _build_communities( |
|
198
|
labels: dict[int, int], |
|
199
|
nodes: dict[int, dict[str, Any]], |
|
200
|
adj: dict[int, list[int]], |
|
201
|
min_size: int, |
|
202
|
) -> list[Community]: |
|
203
|
"""Group nodes by label, compute density, filter by min_size.""" |
|
204
|
groups: dict[int, list[int]] = {} |
|
205
|
for nid, lbl in labels.items(): |
|
206
|
groups.setdefault(lbl, []).append(nid) |
|
207
|
|
|
208
|
communities: list[Community] = [] |
|
209
|
for lbl, members_ids in groups.items(): |
|
210
|
if len(members_ids) < min_size: |
|
211
|
continue |
|
212
|
|
|
213
|
member_set = set(members_ids) |
|
214
|
member_names = [nodes[nid]["name"] for nid in members_ids if nid in nodes] |
|
215
|
|
|
216
|
# Density = actual internal edges / possible internal edges |
|
217
|
internal_edges = sum( |
|
218
|
1 for nid in members_ids for nb in adj.get(nid, []) if nb in member_set |
|
219
|
) |
|
220
|
# Each undirected edge counted twice in the adjacency list |
|
221
|
internal_edges //= 2 |
|
222
|
n = len(members_ids) |
|
223
|
possible = n * (n - 1) / 2 |
|
224
|
density = internal_edges / possible if possible > 0 else 0.0 |
|
225
|
|
|
226
|
communities.append( |
|
227
|
Community( |
|
228
|
name=f"community_{lbl}", |
|
229
|
members=member_names, |
|
230
|
size=len(member_names), |
|
231
|
density=round(density, 4), |
|
232
|
) |
|
233
|
) |
|
234
|
|
|
235
|
communities.sort(key=lambda c: c.size, reverse=True) |
|
236
|
return communities |
|
237
|
|