AI Glossary / Graphs and symbolic AI / Intermediate

Redundancy

Definition

Redundancy, in the supplied bipartite-network context, measures how many pairs of a node's neighbors share another common neighbor. The node redundancy coefficient is the fraction of such pairs among all possible neighbor pairs. It indicates how much of that node's contribution to an unweighted one-mode projection would remain if the node were removed.

What it means

A bipartite network has two kinds of nodes, with connections only between the kinds. For example, employees connect to projects they join. In an employee projection, two employees are linked if they share at least one project.

A project creates projected links between each pair of its participants. Some of those pairs may also work together on other projects. The redundancy coefficient asks what fraction of those pairwise links have that alternative support. It is a specific structural statistic, not a judgment that the project is unnecessary, and it differs from backup capacity or duplicated information in ordinary business language.

How it works

Choose a node v with at least two neighbors. If it has k neighbors, there are k(k−1)/2 unordered pairs. For each pair, check whether its members share a common neighbor other than v. Count a pair once if such an alternative exists, regardless of how many alternatives it has.

Divide the qualifying-pair count by the total pair count. The result lies between zero and one. A value of one means every projected pairwise link generated by v has another source; zero means none does.

The denominator is zero when k is below two, so the coefficient is undefined there under this formula. NetworkX's documented function raises an error when a requested node has fewer than two neighbors. An analysis should handle those cases explicitly instead of silently assigning zero.

Three practical examples

• Project networks: an analyst checks whether pairs of project participants also collaborate on other projects.
• Catalog networks: a researcher links items to descriptive tags and examines whether item pairs sharing one tag also share another.
• Affiliation research: a study links participants to groups and compares how much pairwise overlap depends on individual groups.

Think of it this way

Think of a workshop that introduces several people to one another. Some pairs already meet together elsewhere, while others share only this workshop. Redundancy measures the fraction of pairs with another shared setting. The analogy is limited: a graph edge records the selected relationship, not the quality of a friendship or the practical value of attending the workshop.

Worked example

Create a simple employee - project graph. Project P has employees A, B, C, and D. Project Q has A, B, and C. Project R has C and D. These are the only memberships.

P has four neighbors, so its six neighbor pairs are AB, AC, AD, BC, BD, and CD. Q provides alternative support for AB, AC, and BC. R provides alternative support for CD. Neither AD nor BD has another shared project.

Four of six pairs qualify, so P's redundancy is 4/6 = 2/3, approximately 0.667. Removing P leaves four of its six employee-projection edges and removes AD and BD.

Notice what does not follow. Employees A and D can still be connected by a longer path through C after P is removed. That does not make the direct projected pair AD redundant under this definition; AD needs a shared project of its own. Also, adding another project containing A and B would not increase P's numerator, because AB already counts once.

The memberships and calculations are original. They distinguish projected-edge preservation from general network connectivity and from counting the number of alternative projects.

Illustrative case study

Fictional case: Willow Collaboration Study maps staff memberships in internal working groups. It calculates redundancy for groups with at least two recorded members and keeps smaller groups in a separate undefined category.

A manager initially reads a high coefficient as evidence that a group can be closed. The analyst explains that the metric only concerns overlap in recorded membership pairs. The group may provide a unique decision forum, expertise, or responsibility even if its members meet elsewhere.

The team uses the measure to guide interviews about collaboration patterns, alongside group purpose and activity data. This fictional case illustrates responsible interpretation, not a demonstrated staffing or cost-saving outcome.

Common misconceptions and mistakes

High redundancy does not mean a node has an identical replacement. Different alternative nodes can support different pairs, as Q and R do in the worked example.

It also does not guarantee resilience to several simultaneous removals. The coefficient checks whether another shared neighbor exists, without modeling its reliability or dependence on others.

Do not substitute a longer connecting path for a common neighbor. The definition concerns pairwise links in the projection. Finally, a weighted projection may lose weight when v disappears even if its unweighted edges remain. Preserving edge existence is a weaker statement than preserving the strength of a relationship.

Business use

The coefficient can help describe overlap in affiliation, participation, and classification data. It is most useful when analysts retain the original bipartite structure and explain precisely what each membership edge means.

Before comparing groups, consider their size, data coverage, and observation period. Missing memberships can make alternative support invisible. Report how nodes with fewer than two neighbors were handled, and avoid turning a single structural number into a decision rule about employees or services. Use complementary evidence to investigate why an overlap pattern exists and whether it matters operationally.

People also ask

Does a coefficient of one mean all neighbors share one other node?

No. Different pairs may have different alternative common neighbors. No single replacement is required.

Is redundancy the same as degree?

No. Degree counts neighbors. Redundancy examines overlap among pairs of those neighbors, so equal-degree nodes can have different coefficients.

Can a one-neighbor node have redundancy zero?

The stated ratio is undefined because there are no neighbor pairs. If an application uses a special convention, it should label that convention explicitly.

Check your understanding

In the worked example, why does the longer A - C - D connection not make AD a qualifying pair?

Answer: A and D must share another project directly. A longer path through C does not satisfy that common-neighbor requirement.

Related terms

• bipartite graph
• one-mode projection
• common neighbour
• degree
• affiliation network
• clustering coefficient
• structural overlap
• network robustness

Learn next

draw the employee projection before and after removing P. Then add one project containing A and D and recompute P's coefficient. The new value is 5/6, while a second additional AB project would leave the original coefficient unchanged.

More in Graphs and symbolic AI

• Rectified Linear Unit - A Rectified Linear Unit, usually abbreviated ReLU, is a neural-network activation function defined by ReLU(x) = max(0, x).
• Recursive best-first search - Recursive best-first search, or RBFS, is a heuristic search algorithm that pursues promising paths while limiting memory use.
• Reduct - A reduct, in stable-model logic programming, is a simplified program constructed relative to a proposed set of true atoms.
• Redundant path - A redundant path, in state-space search, is a route to a state that adds no useful advantage over another available route for the search objective.
• Reference controller - A reference controller, in the robotics tracking sense used here, is a controller designed to make a system follow a specified reference path or trajectory.
• Reference counts - In memory-bounded search, reference counts can track how many possible arrivals at a state have already occurred.

Sources

Primary sources: NetworkX defines and documents node redundancy: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.bipartite.redundancy.node_redundancy.html . Latapy, Magnien, and Del Vecchio introduce the measure in their two-mode network analysis: https://www.complexnetworks.fr/wp-content/uploads/2011/01/socnet07.pdf . Scope is the simple, undirected, unweighted bipartite coefficient. Teaching examples are original.

Previous: Reduction operator Next: Redundant path