Must it assign every graph node to a community?

No. A local method may return only a source-centered set.

Can two local communities overlap?

Yes. Separate seed-based searches need not produce a disjoint partition.

Why can adding a connected node reduce the score?

The added node can expose more outward boundary connections, making the resulting boundary less cohesive under the selected measure.

AI Glossary / Graphs and symbolic AI / Intermediate

Local Community Detection

Definition

Local community detection identifies a group of related nodes around a chosen source node in a network. It focuses on the source's surrounding structure rather than necessarily dividing the entire graph into communities. The supplied NetworkX reference illustrates this through greedy source expansion using a local modularity criterion.

What it means

A graph can represent pages and links, documents and similarities, or other entities and relationships. Starting from one relevant entity, local community detection asks which nearby nodes form a structurally cohesive group around it.
There is no single universally correct definition of a community. Different methods use different quality measures and stopping rules. A group found around one source can overlap a group found around another. The output is therefore an algorithm-dependent view of network structure, not automatic proof of a social group, business category, or shared intent.

How it works

A source-expansion method begins with a seed and considers neighboring nodes for inclusion. Under the documented Clauset-style measure, the current community C has a boundary B consisting of members with neighbors outside C. Let T count edges touching B and I count those boundary-touching edges that remain internal to C. Local modularity is R = I/T when the denominator is nonzero.
The documented NetworkX method greedily chooses additions based on this local score and stops when no further improvement is available or a cutoff is reached. This implementation-level stopping rule should not be confused with every variant of the original research algorithm.

Three practical examples

A document network can reveal a candidate topic neighborhood around one selected article.
A software dependency graph can support exploration of a structurally related region around a component, subject to the graph representation chosen.
A product-association network can identify a local group around a selected item for analyst review, without partitioning the full catalog first.

Think of it this way

Think of exploring streets around a landmark and asking where the surrounding neighborhood has a relatively clear boundary. The landmark anchors the exploration. The analogy is limited because graph communities depend on the defined edges and scoring rule; they do not necessarily correspond to geographic areas or formally recognized neighborhoods.

Worked example

Use an invented simple undirected graph with five nodes A, B, C, D, and E. Its edges are AB, AC, BC, CD, and DE. Thus A, B, and C form a triangle, with a path from C through D to E. Every edge is unweighted and counted once in the following arithmetic.
Consider candidate community {A, B}. Both A and B are boundary nodes because they connect to outside node C. The boundary-touching edges are AB, AC, and BC, so T = 3. Only AB is internal, giving I = 1 and R = 1/3.
Now consider {A, B, C}. Only C remains on the boundary because D is outside. The edges touching C are AC, BC, and CD, so T = 3. Two of them, AC and BC, are internal; therefore I = 2 and R = 2/3. Edge AB is internal but does not touch the boundary, so it is not counted in this denominator or numerator.
If D is added, the candidate becomes {A, B, C, D}. The boundary is now D because E remains outside. Boundary-touching edges are CD and DE, giving T = 2. Only CD is internal, so R = 1/2. This addition reduces the score from 2/3 to 1/2.
A policy that requires improvement would reject that proposed addition at this stage. A policy that continues exploration to a fixed size could behave differently. This is a hand-calculated comparison of candidate communities, not a claim that a particular software call was executed or that these candidates are the only possible search history.

Illustrative case study

In a fictional knowledge-management project, Rowan Graph starts from one policy document and expands a local group of linked documents. A reviewer initially treats the returned set as the definitive boundary of a department's responsibilities.
The team explains that the edges represent citation links and that the result depends on the seed, score, and cutoff. It uses the set as an exploration aid and checks important boundary documents manually. This invented case illustrates the difference between a structural grouping and an authoritative organizational classification.

Common misconceptions and mistakes

Local modularity here is not the same as the familiar global modularity Q. In particular, R uses boundary-related edge counts rather than an unrestricted count of all internal edges or the entire graph's edge total.
Do not assume that greedy improvement finds the globally best source-containing community. Ties and seed choice can affect results. Also, the score requires a convention when there is no remaining boundary and T is zero. The original research discusses such cases; a practical implementation's behavior should be checked rather than obtained by dividing zero by zero.

Business use

Local exploration is useful when the business question starts with a particular entity rather than a demand for a complete network partition. Define nodes and edges carefully, since missing links, duplicated records, or an unsuitable relationship definition can change the result substantially.
Record the seed and stopping settings with each result. Compare nearby seeds and review nodes near the boundary to judge stability. If graph direction or weights carry meaning, confirm that the chosen method supports the intended interpretation. Report a discovered group as a candidate structural neighborhood unless independent evidence justifies a stronger domain conclusion.

Check your understanding

Why is edge AB omitted when calculating R for {A, B, C} in the worked example?

Answer: The boundary contains only C. Although AB is internal, neither endpoint is in the boundary, so it is outside the boundary-touching edge set used by this measure.

Related terms

Greedy algorithms
Clustering
Community detection
source node
graph neighborhood
local modularity
greedy algorithm
graph boundary
overlapping communities
global modularity

Learn next

Recalculate the example after adding edge CE. Observe how the extra outward connection changes the score of {A, B, C}. Then compare a strict-improvement stopping rule with a fixed-size exploration rule and explain why their outputs need not match.

Stopping rule

Sources

NetworkX, official greedy_source_expansion documentation: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.community.local.greedy_source_expansion.html Aaron Clauset, Finding local community structure in networks, original paper: https://arxiv.org/pdf/physics/0503036

Previous: Local case-control sampling Next: Local consistency