Graph Algorithms

Centrality and community detection run directly against the database. Both are NetworkX under the hood — GrafitoDB's contribution is scoping the analysis to the right subgraph and resolving results back to nodes.

Centrality

for hit in db.centrality("pagerank", limit=10):
    print(hit["node"].properties["name"], hit["score"])

Results come back sorted, highest first, as {"node": Node, "score": float}.

kind	Answers	Cost
pagerank	Which nodes are reachable from many important nodes?	Fast
degree	Which nodes have the most connections?	Fast
in_degree / out_degree	Directed variants (require directed=True)	Fast
betweenness	Which nodes sit on the most shortest paths?	O(V·E)
closeness / harmonic	Which nodes are near everything else?	Expensive
eigenvector	Like PageRank, undirected-flavoured	Moderate

Degree and PageRank usually agree; betweenness is the one that disagrees, and that disagreement is the point — it finds brokers and bridges that are weakly connected but structurally critical:

# The article that connects two otherwise separate literatures
db.centrality("betweenness", directed=False, limit=5)

On graphs past a few thousand nodes, betweenness gets slow. Pass NetworkX's sampling parameter through, or use pagerank:

db.centrality("betweenness", k=200)  # approximate, sampled from 200 sources

Scoping the Analysis

Every algorithm accepts the same filters, which build the graph the analysis runs on:

db.centrality(
    "pagerank",
    rel_types=["CITES"],                   # only these edge types
    exclude_rel_types=["SEMANTIC_SIMILAR"],# never these
    labels=["Article"],                    # only these node labels
    directed=True,
    weight_property="weight",              # relationship property to weight by
)

Exclude derived edges before analysing

Bulk-generated edges — similarity links, containment, anything produced by a batch job rather than the domain — will dominate any centrality or community result. There are usually far more of them than real edges, and they are distributed by embedding geometry rather than meaning.

# Meaningless: similarity edges swamp the citation structure
db.centrality("pagerank")

# Meaningful
db.centrality("pagerank", rel_types=["CITES"])

The filtering has to happen before the algorithm runs. Post-filtering the results does not undo the effect the extra edges had on the scores.

weight_property reads through to relationship properties, so weight_property="score" finds {"score": 0.9} on the relationship. Edges missing it get weight 1.0. It is rejected for degree-family measures, which count edges and cannot honour a weight.

Communities

for community in db.communities("louvain", seed=42):
    names = [n.properties["name"] for n in community.nodes]
    print(f"community {community.id} ({community.size}): {names}")

Returns Community objects, largest first.

algorithm	Notes
louvain	Default. Fast, good quality, randomised — pass seed.
greedy	Deterministic modularity maximisation. Slower on large graphs.
lpa	Label propagation. Fastest, noisiest, randomised.

resolution tunes granularity for louvain and greedy — higher values produce more, smaller communities:

db.communities("louvain", resolution=1.5, min_size=3, seed=42)

Two properties worth internalising:

• Direction is dropped. Modularity is defined on undirected graphs. Parallel edges collapse into one weighted edge, so two KNOWS edges between the same pair count as weight 2.
• Community ids are positions, not identities. They are indexes into the returned list. Re-running after an edit will renumber them, and louvain/lpa are randomised — pass seed for reproducibility.

Use min_size to drop singletons, which are noise in most datasets.

Naming the Communities

label_terms labels each community with the terms that distinguish it from the others, read from a node property:

for community in db.communities("louvain", seed=42, label_terms=3):
    print(f"[{community.label}] — {community.size} documents")

[graph, nodes, databases] — 3 documents
[search, embeddings, nearest] — 3 documents
[pasta, carbonara, cooking] — 3 documents

This is the cheap end of topic modelling, and worth being clear about what it is not: the clusters come from the graph, and the words only describe whatever landed in each. A community that mixes two subjects gets a label mixing two subjects — the label never fixes a bad partition, it only reports one.

Option	Meaning	Default
label_terms	Terms per community; 0 skips labelling	0
text_property	Node property to read text from	"text"
label_scoring	"tfidf" or "frequency"	"tfidf"
stopwords	Words to exclude	None

tfidf weights a term by how concentrated it is in one community, so words common to all of them fall away on their own. frequency is a plain count and mostly surfaces filler — in the example above it labels two of the three communities with and. That is why stopword lists are rarely needed with tfidf, and unavoidable with frequency.

To keep the labels, write them back as nodes or properties yourself:

for community in db.communities("louvain", seed=42, label_terms=4):
    topic = db.create_node(labels=["Topic"], properties={"name": community.label})
    for node in community.nodes:
        db.create_relationship(topic.id, node.id, "HAS_MEMBER")

Community ids are positions in the result, so materialising them is only meaningful if the graph is not going to change underneath.

Composing with Retrieval

Both methods accept a pre-built NetworkX graph via graph=, which is how they compose with subgraphs — retrieve first, then rank within the result rather than across the whole database:

sub = db.semantic_subgraph("autonomous agents", k=50, expand=1)
central = db.centrality("pagerank", graph=sub.to_networkx(), limit=10)

That is a different question from global PageRank: not "what is important in this database?" but "what is important among the things that matched?".

Exporting the Analysis Graph

to_analysis_graph() returns the filtered NetworkX graph itself, for anything these wrappers do not cover:

import networkx as nx

graph = db.to_analysis_graph(rel_types=["CITES"], weight_property="weight")
nx.diameter(graph.to_undirected())

# Many NetworkX algorithms reject multigraphs; collapse parallel edges first
nx.average_clustering(nx.Graph(graph))

It differs from to_networkx(), which mirrors the entire database unfiltered.

API Reference

grafito.algorithms.Community dataclass

One detected community.

id is the community's index in the returned list (communities are ordered largest first), not a stable identifier across runs — community detection is not deterministic across graph edits.

Source code in grafito/algorithms.py

@dataclass
class Community:
    """One detected community.

    ``id`` is the community's index in the returned list (communities are
    ordered largest first), not a stable identifier across runs — community
    detection is not deterministic across graph edits.
    """

    id: int
    nodes: list[Node]
    size: int
    #: Populated by topic labelling; empty for plain community detection.
    terms: list[str] = field(default_factory=list)
    label: str | None = None

    def ids(self) -> list[int]:
        """Node ids in this community."""
        return [node.id for node in self.nodes]

    def __len__(self) -> int:
        return self.size

ids()

Node ids in this community.

Source code in grafito/algorithms.py

def ids(self) -> list[int]:
    """Node ids in this community."""
    return [node.id for node in self.nodes]

grafito.algorithms.compute_centrality(graph, kind='pagerank', *, weight=None, **kwargs)

Score every node in graph by a centrality measure.

Parameters:

Name	Type	Description	Default
graph	Any	A NetworkX graph.	required
kind	str	One of :data:CENTRALITY_KINDS.	'pagerank'
weight	str | None	Edge attribute to use as weight, or None for unweighted.	None
**kwargs	Any	Passed through to the underlying NetworkX function.	{}

Returns:

Type	Description
dict[int, float]	Mapping of node id to score.

Source code in grafito/algorithms.py

def compute_centrality(
    graph: Any,
    kind: str = "pagerank",
    *,
    weight: str | None = None,
    **kwargs: Any,
) -> dict[int, float]:
    """Score every node in ``graph`` by a centrality measure.

    Args:
        graph: A NetworkX graph.
        kind: One of :data:`CENTRALITY_KINDS`.
        weight: Edge attribute to use as weight, or ``None`` for unweighted.
        **kwargs: Passed through to the underlying NetworkX function.

    Returns:
        Mapping of node id to score.
    """
    nx = _require_networkx()
    if kind not in CENTRALITY_KINDS:
        raise DatabaseError(
            f"Unknown centrality kind '{kind}'. Expected one of: {', '.join(CENTRALITY_KINDS)}"
        )
    if graph.number_of_nodes() == 0:
        return {}

    directed = graph.is_directed()
    if kind in {"in_degree", "out_degree"} and not directed:
        raise DatabaseError(
            f"'{kind}' centrality requires a directed graph; pass directed=True"
        )
    if weight is not None and kind in {"degree", "in_degree", "out_degree"}:
        raise DatabaseError(
            f"'{kind}' centrality counts edges and ignores weights; drop `weight=`"
        )

    if weight is not None:
        # Normalise the weight into the "weight" attribute, reading through the
        # `properties` dict that to_networkx() nests relationship properties in.
        # Without this a weight= naming a relationship property would silently
        # fall back to NetworkX's default of 1 for every edge.
        graph = _as_simple_graph(graph, weight=weight)
        weight = "weight"

    if kind == "pagerank":
        try:
            return nx.pagerank(graph, weight=weight, **kwargs)
        except ImportError:
            # NetworkX routes pagerank through scipy, which GrafitoDB does not
            # depend on — adding it would more than double install size for one
            # measure. Fall back to the same power iteration it implements.
            return _pagerank(graph, weight=weight, **kwargs)
    if kind == "degree":
        return dict(nx.degree_centrality(graph, **kwargs))
    if kind == "in_degree":
        return dict(nx.in_degree_centrality(graph, **kwargs))
    if kind == "out_degree":
        return dict(nx.out_degree_centrality(graph, **kwargs))
    if kind == "betweenness":
        return dict(nx.betweenness_centrality(graph, weight=weight, **kwargs))
    if kind == "closeness":
        # closeness_centrality takes `distance`, not `weight`.
        if weight is not None:
            kwargs.setdefault("distance", weight)
        return dict(nx.closeness_centrality(graph, **kwargs))
    if kind == "harmonic":
        if weight is not None:
            kwargs.setdefault("distance", weight)
        return dict(nx.harmonic_centrality(graph, **kwargs))
    if kind == "eigenvector":
        simple = _as_simple_graph(graph, weight=weight)
        try:
            return dict(nx.eigenvector_centrality(simple, weight="weight", **kwargs))
        except nx.PowerIterationFailedConvergence as exc:
            raise DatabaseError(
                "eigenvector centrality did not converge; try kind='pagerank', "
                "or raise max_iter"
            ) from exc
    raise DatabaseError(f"Unhandled centrality kind '{kind}'")  # pragma: no cover

grafito.algorithms.detect_communities(graph, algorithm='louvain', *, weight=None, resolution=1.0, seed=None, **kwargs)

Partition graph into communities, largest first.

Community detection is defined on undirected graphs, so a directed graph is treated as undirected here: edge direction is dropped, and parallel edges collapse into a single weighted edge. This is a real loss of information — it is inherent to modularity-based methods, not to this wrapper.

Parameters:

Name	Type	Description	Default
graph	Any	A NetworkX graph.	required
algorithm	str	One of :data:COMMUNITY_ALGORITHMS.	'louvain'
weight	str | None	Edge attribute to use as weight, or None for unweighted.	None
resolution	float	Higher values yield more, smaller communities (louvain and greedy only).	1.0
seed	int | None	Seed for the algorithms that are randomised (louvain, lpa), for reproducible partitions.	None

Returns:

Type	Description
list[set[int]]	List of node-id sets, ordered by descending size.

Source code in grafito/algorithms.py

def detect_communities(
    graph: Any,
    algorithm: str = "louvain",
    *,
    weight: str | None = None,
    resolution: float = 1.0,
    seed: int | None = None,
    **kwargs: Any,
) -> list[set[int]]:
    """Partition ``graph`` into communities, largest first.

    Community detection is defined on undirected graphs, so a directed graph is
    treated as undirected here: edge direction is dropped, and parallel edges
    collapse into a single weighted edge. This is a real loss of information —
    it is inherent to modularity-based methods, not to this wrapper.

    Args:
        graph: A NetworkX graph.
        algorithm: One of :data:`COMMUNITY_ALGORITHMS`.
        weight: Edge attribute to use as weight, or ``None`` for unweighted.
        resolution: Higher values yield more, smaller communities
            (``louvain`` and ``greedy`` only).
        seed: Seed for the algorithms that are randomised (``louvain``, ``lpa``),
            for reproducible partitions.

    Returns:
        List of node-id sets, ordered by descending size.
    """
    nx = _require_networkx()
    if algorithm not in COMMUNITY_ALGORITHMS:
        raise DatabaseError(
            f"Unknown community algorithm '{algorithm}'. "
            f"Expected one of: {', '.join(COMMUNITY_ALGORITHMS)}"
        )
    if graph.number_of_nodes() == 0:
        return []

    # _as_simple_graph normalises whatever `weight` named into "weight".
    undirected = _as_simple_graph(graph, weight=weight, undirected=True)

    if algorithm == "louvain":
        groups = nx.community.louvain_communities(
            undirected, weight="weight", resolution=resolution, seed=seed, **kwargs
        )
    elif algorithm == "greedy":
        groups = nx.community.greedy_modularity_communities(
            undirected, weight="weight", resolution=resolution, **kwargs
        )
    else:  # lpa / label_propagation
        if seed is not None:
            kwargs.setdefault("seed", seed)
        groups = nx.community.asyn_lpa_communities(undirected, weight="weight", **kwargs)

    result = [set(group) for group in groups]
    result.sort(key=len, reverse=True)
    return result