An independent study reference written by Dr Phuc V. Nguyen. It is not official subject material — for assessment requirements always follow your subject outline and vUWS.

Networksintermediate

Bridges, cliques and components

Q: An analyst reports that a 5,000-node customer referral network has an average path length of 4.2 steps. It later emerges that only the largest component was analysed, and it holds 3,100 nodes. What is the problem?

The statistic describes 62 per cent of the customers and was presented as if it described all of them. Path-based statistics can only be computed within a component, so restricting to the largest one is standard practice. The failure is in the reporting. Around 1,900 customers sit outside that component and are not described by the figure at all, and whether they are isolates or small clusters changes what the number means.

Q: A team wants to reduce the risk that the failure of a single supply link halts production. Which structural feature should they look for first?

Ties that are bridges, since each is the only route between two parts of the network. Continuity risk sits on the ties that have no alternative route. Removing a bridge splits the network, so bridges are the links to duplicate first. Had the question been about losing a supplier rather than a link, the matching feature would be an articulation point, the node version of the same idea. A clique indicates redundancy, which is the opposite of the risk. Average degree and isolate counts describe the network without locating the fragile link.

Three structural ideas describe the shape of a network beyond any centrality score. A component is a set of actors who can all reach each other, and a network can hold several with no path between them. A bridge is a tie whose removal increases the number of components, so it is the only route between two parts. The actor version is an articulation point, a node whose removal splits the network. A clique is a set of actors where every single pair is tied, the densest sub-structure possible. Together they answer questions centrality cannot: is the network whole, where is it fragile, and which groups are effectively closed.

Why it matters

Look at a network as an island chain. Components are the separate islands. A bridge is the single causeway. A clique is a village where everybody knows everybody. You can say a lot about how news travels from those three features alone, before computing anything about individuals. Cut the causeway and half the chain stops hearing from the other half.

Before you read on — recall

An analyst reports that a 5,000-node customer referral network has an average path length of 4.2 steps. It later emerges that only the largest component was analysed, and it holds 3,100 nodes. What is the problem?

Formulas

Local clustering coefficient

C_i = \frac{2 e_i}{k_i (k_i - 1)}

Here

k_i

is the number of neighbours of actor

i

and

e_i

is the number of ties among those neighbours. It measures how close a neighbourhood comes to being a clique. Ana has neighbours Ben, Cara and Dan with only one tie among them, Ben-Cara, so

C_{\text{Ana}} = \tfrac{2 \times 1}{3 \times 2} \approx 0.33

. Every definition on this page is written for a simple undirected relation. On a directed one, components split into weakly connected, where direction is ignored, and strongly connected, where every actor can reach every other along the arrows, and the two counts often differ.

Ties inside a clique of size g

L_{\text{clique}} = \frac{g(g-1)}{2}

A clique is complete, so it holds every possible pair. A clique of 5 holds 10 ties and a clique of 10 holds 45. That is why a handful of overlapping cliques can lift whole-network density sharply while most actors stay poorly connected.

Worked examples

Scenario

The running six-person team is checked for fragility. Its ties are Ana-Ben, Ana-Cara, Ana-Dan, Ben-Cara, Dan-Eve and Eve-Finn.

Solution

The network is one component, so everybody can reach everybody. Three ties are bridges: Ana-Dan, Dan-Eve and Eve-Finn. Removing any of them splits the team. Ana-Ben is not a bridge, because Ana and Ben stay connected through Cara. The only clique larger than a pair is Ana-Ben-Cara, a triangle. Ana, Dan and Eve are each articulation points, since removing any one of them leaves two components. So the team is one tight trio hanging off a thin chain with three weak joints along it, not a single one. That whole reading comes from structure, with no centrality score computed.

Scenario

A retailer maps which products are bought together and finds one giant component of 4,000 products, about 60 small components of 3 to 8 products each, and 900 products with no co-purchase at all.

Solution

Each part suggests a different action. The giant component is where cross-sell recommendations work, because paths exist between items. The small components are self-contained niches, often seasonal or specialist, and recommending into them from the main body will misfire. The 900 isolates are bought alone, so they need their own merchandising rather than a recommender. Reporting only the giant component, which is common, would quietly hide more than a fifth of the catalogue. The small components hold between 180 and 480 products and the isolates another 900, so between 1,080 and 1,380 products out of roughly 5,100 to 5,400 sit outside the giant component.

Common mistakes

✗A clique is just a tightly knit group. In network terms a clique has an exact definition, a set in which every single pair is tied. Groups that feel cohesive usually fall short of that, which is why analysts use relaxed forms such as k-cores, or community detection, rather than strict cliques.
✗Community detection finds cliques. Community detection partitions a network into groups that are denser inside than between, and those groups are almost never complete. The two answer different questions and can disagree, so always name which one produced a result.
✗A bridge is the same thing as a high-betweenness actor. A bridge is a tie, betweenness is a property of an actor, and the actor-level counterpart of a bridge is an articulation point. They are related and distinct, and a network can contain high-betweenness brokers with no bridges and no articulation points at all, if every gap has a second and longer route.
✗Isolates are noise and can be dropped. An isolate is a finding. It may mean a genuinely disconnected actor, or it may mean that person never responded. Dropping them without checking converts a data problem into a structural conclusion, and it changes every density and centrality score computed afterwards.

Revision bullets

•A component is a set of mutually reachable actors; an isolate is a component of one
•A bridge is a tie whose removal increases the number of components; an articulation point is the node version
•A clique is complete: every pair tied, so g(g-1)/2 ties inside
•The clustering coefficient measures how clique-like a neighbourhood is
•Running example: one component, three bridges, one triangle
•Community detection returns dense groups, not complete ones

Quick check

A team wants to reduce the risk that the failure of a single supply link halts production. Which structural feature should they look for first?

Connected topics

What SNA Is Weighted Ties Closeness Betweenness Density Filter Bubbles

More in Networks

Actors and Ties Degree Centrality Network Study

Sources

Luce & Perry (1949)
Luce, R. D., & Perry, A. D. "A Method of Matrix Analysis of Group Structure." Psychometrika, 14(2), 95-116, 1949.
Origin of the clique as a formally defined complete sub-group.
Granovetter (1973)
Granovetter, M. S. "The Strength of Weak Ties." American Journal of Sociology, 78(6), 1360-1380, 1973.
Introduces bridges and local bridges and links them to which information reaches which group.
Watts & Strogatz (1998)
Watts, D. J., & Strogatz, S. H. "Collective Dynamics of Small-World Networks." Nature, 393, 440-442, 1998.
Source of the clustering coefficient used here as a measure of local cliquishness.
Newman & Girvan (2004)
Newman, M. E. J., & Girvan, M. "Finding and Evaluating Community Structure in Networks." Physical Review E, 69, 026113, 2004.
Sets out modularity-based community detection, the practical alternative to strict cliques.

How to cite this page

Dr. Phil's Quant Lab. (2026). Bridges, cliques and components. Derivatives Atlas. https://phucnguyenvan.com/concept/ba-bridges-cliques-components