💻 computer science

Proportional Selection in Networks

This paper proposes and theoretically analyzes two approaches for selecting $k$ representative nodes from a network that simultaneously identify the most influential nodes and ensure the selection proportionally reflects the network's diversity, with effectiveness validated through experiments.

Original authors: Georgios Papasotiropoulos, Oskar Skibski, Piotr Skowron, Tomasz Wąs

Published 2026-05-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Georgios Papasotiropoulos, Oskar Skibski, Piotr Skowron, Tomasz Wąs

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are organizing a big party and need to pick a small group of "representatives" from a huge crowd of guests to help plan the event. You have two main goals:

Find the most popular people: You want to pick the guests who know the most people and can influence the biggest part of the crowd.
Be fair to all groups: You don't want to pick 10 people just from the "Sports Fan" section of the room, even if they are the most popular. You want your committee to look like the room itself. If 50% of the room loves sports, 30% loves music, and 20% loves art, your committee should reflect that mix.

This paper tackles a problem where traditional methods fail at the second goal. Usually, algorithms just pick the "most popular" people (like the biggest celebrities). But in a network, a few super-connected people can dominate, causing smaller groups to be completely ignored.

Here is how the authors fix this, using simple analogies:

The Problem: The "Rich Get Richer" Effect

Think of a network like a map of cities connected by roads.

Old Method (TopRank/TopKatz): Imagine you are trying to find the best cities to visit. The old method says, "Go to the city with the most roads leading to it."
- The Flaw: If one city has a massive highway system connecting it to a huge region, it gets picked every time. Meanwhile, a smaller, cozy town with a great community might have fewer roads leading to it, so it never gets picked, even though it represents a huge chunk of the population. The result? Your travel guide only covers the big city, ignoring the rest of the country.

The Solution: A Fair Voting System

The authors propose a new way to pick these representatives. They treat the network like an election where everyone votes for everyone else based on how connected they are.

Turning Connections into Votes: Instead of just counting how many roads lead to a city, they imagine every person in the network casting a vote. If you are close to someone, you vote for them.
The "Equal Shares" Rule: This is the secret sauce. They use a voting rule called Method of Equal Shares (MES).
- The Analogy: Imagine every person in the room gets a tiny bucket of water (a budget). To elect a representative, that person needs to pay for it.
- If a big group of people (say, the "Sports Fans") all want the same person, they can pool their water buckets to pay for that person.
- Crucially, once they pay for one person, their buckets get smaller. This prevents the big group from buying everyone on the committee. They have to save some water to buy representatives for their other favorite people.
- This forces the system to spread the "seats" around so that the Sports Fans, Music Fans, and Art Fans all get a fair share of the committee, proportional to their size in the room.

The Two "Flavors" of the Method

The paper tests two different ways to measure "popularity" (centrality) before applying the fair voting rule:

The "PageRank" Flavor: This is like a game of "pass the buck." If you pass a vote to someone, that vote gets split up and shared among all the people they pass it to. It's very democratic but can sometimes be too cautious, diluting the influence of very popular people.
The "Katz" Flavor: This is like a direct endorsement. If you pass a vote to someone, the full weight of that vote goes to them. It's more direct and often better at finding the truly influential leaders, but without the fair voting rule, it can be very unfair to small groups.

The authors combine these popularity measures with the "Equal Shares" voting rule. They call their new methods MesRank and MesKatz.

What They Found

The authors tested this on real-world data, like:

College Football Teams: Where teams are grouped by conferences.
- Old Way: Picked 3 teams from one big conference and ignored the others.
- New Way: Picked teams from almost every conference, respecting the size of each group.
Political Blogs: Where blogs are either "Liberal" or "Conservative."
- Old Way: If one side was slightly more popular, they took up the whole committee.
- New Way: The committee reflected the actual balance of the two sides, even if one side was slightly smaller.

The Big Takeaway

You don't need to know who belongs to which group (like "Sports Fan" or "Liberal") to make it fair. The algorithm looks only at the structure of the connections. It figures out, "Oh, these 50 people are all tightly connected to each other and separate from the others," and automatically ensures they get a fair number of seats on the committee.

In short: They built a system that finds the most influential people in a network but forces the selection process to be mathematically fair to every distinct group within that network, without needing to know the groups' names or labels in advance.

Technical Summary: Proportional Selection in Networks

Problem Definition
The paper addresses the problem of selecting a subset of $k$ representative nodes from a network $G=(V, E)$ . The objective is twofold: to identify the most influential nodes (based on centrality) and to ensure that the selection proportionally reflects the structural diversity of the network. A critical constraint is that the selection must be feature-blind; the algorithms cannot rely on explicit node attributes (e.g., demographic labels, political affiliation) or pre-defined community memberships. Instead, proportional guarantees must be derived solely from the graph topology. This contrasts with existing "feature-aware" fairness approaches which require known group attributes, and "diversity" approaches which may over-represent small, disconnected groups at the expense of large cohesive communities.

Methodology
The authors propose a general framework that bridges network science (centrality measures) and computational social choice (proportional committee election rules).

Transformation to Election: The framework transforms the network selection problem into a committee election where the set of candidates $C$ is identical to the set of voters $V$ .
Utility Definition: For any two distinct nodes $u$ $u$ and $v$ $v$ , a utility function $\mu(u, v)$ $μ (u, v)$ is defined based on a chosen centrality measure.
- For PageRank (with decay factor $\alpha$ ), $\mu(u, v)$ represents the expected number of visits to $v$ by a random walk starting at $u$ .
- For Katz centrality, the utility is defined analogously based on the sum of walks.
- This utility quantifies how much node $u$ "supports" node $v$ based on reachability and structural importance.
Selection Rules: The framework applies proportional election rules to this constructed election:
- MesRank / MesKatz: Utilizes the Method of Equal Shares (MES), a rule known for satisfying strong proportionality axioms (e.g., Extended Justified Representation).
- BosRank / BosKatz: Utilizes the Method of Equal Shares with Bounded Overspending (BOS), a variant designed to handle high variance in utilities while maintaining proportionality.
- Baselines: The authors compare these against TopRank and TopKatz, which simply select the $k$ nodes with the highest centrality scores (equivalent to Approval Voting or Satisfaction Approval Voting in the election analogy).

Theoretical Analysis
The paper provides an axiomatic analysis of the proposed methods on specific graph classes and general graphs:

Bipartite Graphs: In graphs mimicking representative democracy (voters vs. candidates), TopRank and TopKatz fail to provide proportional representation, often selecting all $k$ nodes from the largest group. In contrast, MesRank and MesKatz select nodes proportional to the size of the voter groups.
Functional Graphs: In graphs representing delegation structures (e.g., LiquidFeedback), TopRank tends to select nodes from a single large in-tree, whereas MesRank distributes selections proportionally across different in-trees.
Axiomatic Guarantees: The authors define Clique-Entitlement, Component-Entitlement, and Subgraph-Entitlement. They prove that MesRank and MesKatz satisfy Group-Entitlement, a property analogous to Proportional Justified Representation (PJR). This guarantees that any sufficiently large, cohesive group of nodes (with significant overlap in their successors) receives a proportional number of representatives in the output. TopRank and TopKatz violate these axioms.

Experimental Results
The authors evaluate the methods on synthetic and real-world datasets:

Efficiency: The proposed methods run in polynomial time ( $O(kn^2)$ for MES, $O(mn)$ for centrality), scaling significantly better than local search group-closeness centrality.
College Football Network: On a network of teams and conferences, TopKatz selects multiple teams from a single conference, ignoring others. MesKatz and BosKatz distribute selections evenly across conferences, matching the underlying community structure.
Political Blogs: On a network of liberal and conservative blogs, the authors simulate data imbalance by removing nodes. TopRank/TopKatz significantly underrepresent the minority group as the imbalance increases. In contrast, BosKatz closely tracks the input label distribution, providing near-perfect proportional representation while maintaining high influence (measured by summed centrality and independent cascade spread).
Euclidean Data: In synthetic graphs modeling ideological spectra and competence bias, BosRank and BosKatz most accurately reflect the original population proportions. TopKatz often fails to provide any proportionality, while PageRank-based TopRank shows some inherent proportionality but still underperforms compared to the election-based methods.

Key Contributions and Significance
The paper claims the following contributions:

Feature-Blind Proportionality: It introduces the first framework for proportional node selection that relies exclusively on network topology, avoiding the need for explicit group labels or attributes.
General Framework: It demonstrates how to extend any centrality measure (or custom importance model) into a proportional selection rule by mapping the network to a committee election.
Theoretical Guarantees: It establishes that these methods satisfy strong proportionality axioms (Group-Entitlement) that standard centrality-based selection (TopRank/TopKatz) fails to meet.
Empirical Effectiveness: Experiments show that while standard centrality measures (especially Katz) can severely neglect minority groups, the proposed election-based methods (particularly those using BOS) achieve fair representation across diverse network structures while still selecting highly influential nodes.

The authors note that while PageRank inherently exhibits some proportional behavior due to its dampening mechanism, it can still lead to undesirable outcomes (e.g., favoring "extremist" nodes with fewer outgoing edges). The proposed framework mitigates these limitations by allowing the integration of various centrality measures or machine learning models while enforcing proportional representation through the election mechanism.