pith. sign in

arxiv: 2502.03545 · v2 · pith:NOOZQ3GGnew · submitted 2025-02-05 · 💻 cs.GT · cs.AI· cs.MA· cs.SI

Proportional Selection in Networks

Georgios Papasotiropoulos , Oskar Skibski , Piotr Skowron , Tomasz W\k{a}s This is my paper

Pith reviewed 2026-05-23 03:40 UTC · model grok-4.3

classification 💻 cs.GT cs.AIcs.MAcs.SI
keywords node selectioninfluence maximizationproportional diversitynetwork representationsocial networksfair selection
0
0 comments X

The pith

Two methods select influential nodes while reflecting network diversity proportionally.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines how to pick k nodes from a network that both spread influence widely and mirror the network's group proportions. It develops two separate approaches that pursue these goals together. Theoretical examination checks the soundness of each method. Experiments on real and synthetic networks test whether the selections succeed in practice. Readers care because many network decisions, from marketing to information spread, require both reach and fairness to avoid ignoring parts of the structure.

Core claim

We address the problem of selecting k representative nodes from a network, aiming to achieve two objectives: identifying the most influential nodes and ensuring the selection proportionally reflects the network's diversity. We propose two approaches to accomplish this, analyze them theoretically, and demonstrate their effectiveness through a series of experiments.

What carries the argument

Two approaches that jointly optimize influence maximization and proportional diversity when choosing k nodes.

If this is right

  • The chosen nodes spread influence while their group counts match the network proportions.
  • Theoretical properties of the two methods hold for the combined objective.
  • Experiments confirm the methods produce usable selections on varied networks.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same selection logic might apply to time-varying networks where group sizes shift.
  • Platform designers could use the methods to pick seed users for campaigns that reach underrepresented communities.
  • One could test whether the two approaches differ in speed on very large graphs.

Load-bearing premise

That a meaningful and computable notion of proportional diversity exists for general networks that can be jointly optimized with influence without one objective rendering the other meaningless or trivial.

What would settle it

Apply both methods to a network where high-influence nodes all belong to one group and check whether any output set satisfies both goals at once.

Figures

Figures reproduced from arXiv: 2502.03545 by Georgios Papasotiropoulos, Oskar Skibski, Piotr Skowron, Tomasz W\k{a}s.

Figure 1
Figure 1. Figure 1: Selecting k nodes from a bipartite graph. TopRank (red double lines) and AbsorbRank (green shading) select k nodes from the first group of V2. MesRank (blue pattern) selects 0.4k of nodes from the first group and 0.3k from each other group of V2. 4 Case Studies In this section, we illustrate our methods using two specific classes of graphs: bipartite and functional, as defined in Section 2. In these graph … view at source ↗
Figure 2
Figure 2. Figure 2: Selecting k nodes from the n-path (n divisible by k). Top-Rank (red double lines) and MesRank (blue pattern) choose the last k nodes. AbsorbRank (green shading) selects nodes evenly splitting the path [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Selecting k = 5 nodes from a (directed in-)tree with two unbalanced branches of equal size. TopRank (red double lines) selects mostly from the right-hand side. MesRank (blue pattern) selects two nodes from each side. AbsorbRank (green shading) splits the tree in subtrees of size 3. 4.2 Functional Graphs We now consider graphs in which every node has out-degree of at most one. PageRank and Katz centralities… view at source ↗
Figure 4
Figure 4. Figure 4: The College Football Network, where each group of nodes represents one of 11 conferences or a group of [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Maximum number of nodes from one conference that are selected by our rules for a given committee size in [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The fraction of nodes with the minority label in the graph (gray dashed lines) and in the rule outputs (lines [PITH_FULL_IMAGE:figures/full_fig_p009_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Histograms generated by our PageRank-based methods for Euclidean graphs. The distributions (first row) are [PITH_FULL_IMAGE:figures/full_fig_p011_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Histograms generated by our Katz-based methods for Euclidean graphs. The distributions (first row) are [PITH_FULL_IMAGE:figures/full_fig_p012_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: An example demonstrating that TopRank and TopKatz violate Clique-Entitlement (Proposition 3). Nodes with red double lines have the highest PageRank and Katz centrality. 1 2 3 4 5 6 [PITH_FULL_IMAGE:figures/full_fig_p018_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: A component of the graph used in the proof that [PITH_FULL_IMAGE:figures/full_fig_p018_10.png] view at source ↗
read the original abstract

We address the problem of selecting $k$ representative nodes from a network, aiming to achieve two objectives: identifying the most influential nodes and ensuring the selection proportionally reflects the network's diversity. We propose two approaches to accomplish this, analyze them theoretically, and demonstrate their effectiveness through a series of experiments.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper addresses the problem of selecting k representative nodes from a network to achieve both identifying the most influential nodes and ensuring the selection proportionally reflects the network's diversity. It proposes two approaches, analyzes them theoretically, and demonstrates their effectiveness through experiments.

Significance. If the proposed approaches successfully balance influence maximization and proportional diversity, the work would contribute to network analysis by addressing the joint optimization of these objectives, which are often in tension.

major comments (1)
  1. [Abstract] Abstract: The abstract states that theoretical analysis and experiments support the claims, but provides zero equations, definitions, or result details; therefore the actual support for the central claim cannot be evaluated.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their review. We address the single major comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract: The abstract states that theoretical analysis and experiments support the claims, but provides zero equations, definitions, or result details; therefore the actual support for the central claim cannot be evaluated.

    Authors: We agree that the provided abstract is high-level and contains no equations, formal definitions, or quantitative results. This is a fair observation. We will revise the abstract to incorporate a concise statement of the two proposed approaches, the key theoretical guarantees (e.g., approximation ratios), and a brief summary of the main experimental findings, while remaining within typical length limits. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained at presented level

full rationale

The provided abstract and context describe a high-level proposal of two approaches for joint influence maximization and proportional diversity selection in networks, supported by theoretical analysis and experiments. No equations, parameter definitions, self-citations, or derivation steps are quoted or visible. Per the hard rules, circularity can only be claimed when a specific reduction is exhibited by quoting the paper (e.g., a fitted input renamed as prediction or self-citation load-bearing the central claim). Absent any such content, an honest non-finding applies; the work is treated as self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract supplies no information on free parameters, axioms, or invented entities.

pith-pipeline@v0.9.0 · 5576 in / 929 out tokens · 26365 ms · 2026-05-23T03:40:10.871269+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

40 extracted references · 40 canonical work pages

  1. [1]

    L. A. Adamic and N. Glance. The political blogosphere and the 2004 U . S . election: divided they blog. In Proceedings of the International Workshop on Link Discovery, page 36–43, 2005

    work page 2004

  2. [2]

    N. Alon, F. Fischer, A. Procaccia, and M. Tennenholtz. Sum of us: Strategyproof selection from the selectors. In Proceedings of the Conference on Theoretical Aspects of Rationality and Knowledge, pages 101--110, 2011

    work page 2011

  3. [3]

    u gner, S. G \

    E. Angriman, A. van der Grinten, A. Bojchevski, D. Z \"u gner, S. G \"u nnemann, and H. Meyerhenke. Group centrality maximization for large-scale graphs. In Proceedings of the workshop on Algorithm Engineering and Experiments, pages 56--69, 2020

    work page 2020

  4. [4]

    Angriman, R

    E. Angriman, R. Becker, G. d'Angelo, H. Gilbert, A. van Der Grinten, and H. Meyerhenke. Group-harmonic and group-closeness maximization--approximation and engineering. In Proceedings of the Workshop on Algorithm Engineering and Experiments, pages 154--168, 2021

    work page 2021

  5. [5]

    H. Aziz, O. Lev, N. Mattei, J. Rosenschein, and T. Walsh. Strategyproof peer selection: Mechanisms, analyses, and experiments. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 397--403, 2016

    work page 2016

  6. [6]

    H. Aziz, M. Brill, V. Conitzer, E. Elkind, R. Freeman, and T. Walsh. Justified representation in approval-based committee voting. Social Choice and Welfare, 48 0 (2): 0 461--485, 2017

    work page 2017

  7. [7]

    H. Aziz, B. E. Lee, S. M. Chu, and J. Vollen. Proportionally representative clustering. In Proceedings of the Conference on Web and Internet Economics, 2024

    work page 2024

  8. [8]

    Boldi, F

    P. Boldi, F. Bonchi, C. Castillo, and S. Vigna. Viscous democracy for social networks. Communications of the ACM, 54 0 (6): 0 129--137, 2011

    work page 2011

  9. [9]

    Bonacich

    P. Bonacich. Factoring and weighting approaches to status scores and clique identification. Journal of mathematical sociology, 2 0 (1): 0 113--120, 1972

    work page 1972

  10. [10]

    M. Brill. Interactive democracy. In Proceedings of the International Conference on Autonomous Agents and MultiAgent Systems (Blue Sky Ideas Track), pages 1183--1187, 2018

    work page 2018

  11. [11]

    Brin and L

    S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine. Computer networks and ISDN systems, 30 0 (1-7): 0 107--117, 1998

    work page 1998

  12. [12]

    C. Chen, W. Wang, and X. Wang. Efficient maximum closeness centrality group identification. In Proceedings of the Australasian Database Conference, pages 43--55, 2016

    work page 2016

  13. [13]

    X. Chen, B. Fain, L. Lyu, and K. Munagala. Proportionally fair clustering. In Proceedings of the International Conference on Machine Learning, pages 1032--1041, 2019

    work page 2019

  14. [14]

    Dasgupta, C

    S. Dasgupta, C. H. Papadimitriou, and U. Vazirani. Algorithms. McGraw-Hill, Inc., 2006

    work page 2006

  15. [15]

    Elkind, P

    E. Elkind, P. Faliszewski, J. Laslier, P. Skowron, A. Slinko, and N. Talmon. What do multiwinner voting rules do? An experiment over the two-dimensional E uclidean domain. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 494--501, 2017

    work page 2017

  16. [16]

    M. G. Everett and S. P. Borgatti. The centrality of groups and classes. Journal of mathematical sociology, 23 0 (3): 0 181--201, 1999

    work page 1999

  17. [17]

    Faliszewski, P

    P. Faliszewski, P. Skowron, A. Slinko, and N. Talmon. Multiwinner voting: A new challenge for social choice theory. In Trends in Computational Social Choice. AI Access, 2017

    work page 2017

  18. [18]

    Faliszewski, J

    P. Faliszewski, J. Flis, D. Peters, G. Pierczynski, P. Skowron, D. Stolicki, S. Szufa, and N. Talmon. Participatory budgeting: Data, tools and analysis. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 2667--2674, 2023

    work page 2023

  19. [19]

    G. N. Frederickson. Optimal algorithms for tree partitioning. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pages 168--177, 1991

    work page 1991

  20. [20]

    Girvan and M

    M. Girvan and M. E. J. Newman. Community structure in social and biological networks. Proceedings of the National Academy of Sciences, 99 0 (12): 0 7821--7826, 2002

    work page 2002

  21. [21]

    Green-Armytage

    J. Green-Armytage. Direct voting and proxy voting. Constitutional Political Economy, 26: 0 190--220, 2015

    work page 2015

  22. [22]

    Holzman and H

    R. Holzman and H. Moulin. Impartial nominations for a prize. Econometrica, 81 0 (1): 0 173--196, 2013

    work page 2013

  23. [23]

    D. Jin, Z. Yu, P. Jiao, S. Pan, D. He, J. Wu, S. Y. Philip, and W. Zhang. A survey of community detection approaches: From statistical modeling to deep learning. IEEE Transactions on Knowledge and Data Engineering, 35 0 (2): 0 1149--1170, 2021

    work page 2021

  24. [24]

    L. Katz. A new status index derived from sociometric analysis. Psychometrika, 18 0 (1): 0 39--43, 1953

    work page 1953

  25. [25]

    Lackner and P

    M. Lackner and P. Skowron. Multi-Winner Voting with Approval Preferences. Springer Briefs in Intelligent Systems. Springer, 2023

    work page 2023

  26. [26]

    A. N. Langville and C. D. Meyer. Google's PageRank and beyond: The science of search engine rankings. Princeton University Press, 2006

    work page 2006

  27. [27]

    Laslier and M

    J.-F. Laslier and M. R. Sanver, editors. Handbook on Approval Voting. Springer, 2010

    work page 2010

  28. [28]

    B. Li, L. Li, A. Sun, C. Wang, and Y. Wang. Approximate group fairness for clustering. In Proceedings of the International Conference on Machine Learning, pages 6381--6391, 2021

    work page 2021

  29. [29]

    J. H. Michael. Labor dispute reconciliation in a forest products manufacturing facility. Forest Products Journal, 47 0 (11/12): 0 41, 1997

    work page 1997

  30. [30]

    L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical Report 1999-66, Stanford InfoLab, 1999

    work page 1999

  31. [31]

    Papasotiropoulos, S

    G. Papasotiropoulos, S. Z. Pishbin, O. Skibski, P. Skowron, and T. . Method of equal shares with bounded overspending. arXiv preprint arXiv:2409.15005, 2024

    work page arXiv 2024

  32. [32]

    Perl and S

    Y. Perl and S. R. Schach. Max-min tree partitioning. Journal of the ACM, 28 0 (1): 0 5--15, 1981

    work page 1981

  33. [33]

    Peters and P

    D. Peters and P. Skowron. Proportionality and the limits of welfarism. In Proceedings of the ACM Conference on Economics and Computation, pages 793--794, 2020

    work page 2020

  34. [34]

    Peters, G

    D. Peters, G. Pierczy \'n ski, and P. Skowron. Proportional participatory budgeting with additive utilities. In Proceedings of the Conference on Neural Information Processing Systems, pages 12726--12737, 2021

    work page 2021

  35. [35]

    R. A. Rossi and N. K. Ahmed. The network data repository with interactive graph analytics and visualization. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 4292--4293, 2015. https://networkrepository.com

    work page 2015

  36. [36]

    Rozemberczki, C

    B. Rozemberczki, C. Allen, and R. Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9 0 (2), 2021

    work page 2021

  37. [37]

    J. R. Seeley. The net of reciprocal influence. a problem in treating sociometric data. Canadian Journal of Experimental Psychology, 3: 0 234, 1949

    work page 1949

  38. [38]

    T. and O. Skibski. An axiom system for feedback centralities. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 443--449, 2021

    work page 2021

  39. [39]

    T. and O. Skibski. Axiomatic characterization of pagerank. Artificial Intelligence, 2023. 103900

    work page 2023

  40. [40]

    J. Zhao, J. C. Lui, D. Towsley, and X. Guan. Measuring and maximizing group closeness centrality over disk-resident graphs. In Proceedings of the International Conference on World Wide Web, pages 689--694, 2014

    work page 2014