Pith. sign in

REVIEW 2 major objections 4 minor 65 references

Q-DISCO: Query-Centric Densest Subgraphs in Networks with Opinion Information

T0 review · 2 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper introduces Q-DISCO, proves the query-centric densest-subgraph problem is NP-hard and ETH-hard to approximate, and shows two heuristics that return dense query-aligned subgraphs in practice.

desk verdict Q-DISCO is a well-posed new primitive with sound hardness results and two practical heuristics; the main weakness is the unvalidated opinion labels in the Twitter case study, not the algorithmics. read the letter →

arxiv 2412.11647 v1 pith:4KXNE7Z2 submitted 2024-12-16 cs.SI physics.soc-ph

Tianyi Chen , Atsushi Miyauchi , Charalampos E. Tsourakakis This is my paper · ORCID
classification cs.SIphysics.soc-ph MSC 68R1068Q1705C8590C27
keywords Q-DISCOdensestsubgraphopinionminingagreementconstraintNP-hardnessLagrangianrelaxationgreedypeelingsocialnetworkanalysis
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper introduces Q-DISCO, a formulation for opinion-labeled networks that asks for the densest subgraph whose nodes' average agreement with a query opinion vector is at least a threshold. The paper proves the problem is NP-hard even when every agreement is 0 or 1, and that under the Exponential Time Hypothesis no polynomial-time algorithm can approximate it within a factor of $n^{1/(\log\log n)^c}$ for some $c>0$. Because a practically acceptable approximation ratio is therefore out of reach, the authors design two heuristics: Q-Lagrange, built on a Lagrangian relaxation that becomes a weighted densest-subgraph instance solvable in strongly polynomial time, and Q-Peeling, a greedy peeling rule guided by the dual of a linear-programming relaxation. Both come with a-posteriori guarantees that become tight as the returned subgraph's agreement approaches the threshold, and the experiments show Q-Peeling finds denser query-aligned subgraphs than filtering or LP-rounding baselines on real social, co-authorship, and music-friendship networks. If the formulation is accepted, the paper provides a scalable primitive for locating cohesive opinion groups, compatible communities, or polarization niches.

What carries the argument

The machinery is the pair 'density objective plus agreement constraint', measured through the per-node agreement $c_v=\boldsymbol{p}_v\cdot\boldsymbol{q}$ and the average agreement $c(S)$. Q-Lagrange's engine is the Lagrangian relaxation $\max_{S\subseteq V}\ d(S)+\lambda(c(S)-\theta)$, which is exactly a weighted densest-subgraph problem with positive and negative node weights; the relaxation value $J(\lambda)$ is a piecewise-linear convex function, so binary search on $\lambda$ locates the smallest multiplier whose solution respects the constraint, and each evaluation uses a strongly-polynomial max-flow-based routine. Q-Peeling's engine is the dual of an LP relaxation of Q-DISCO, interpreted as a load-balancing problem: each node's load is $\deg_{V'}(v)+z_2(c_v-\theta)$, the peeling order removes minimum-load nodes, and the highest-load prefix set $T$ yields an upper bound on OPT; binary search on $z_2$ then steers toward feasible, dense prefixes. The load definition is what lets the algorithms trade edge density against opinion alignment in a single scalar.

What would settle it

Construct a graph with two planted cliques of equal density: one whose members share a queried stance but have opinion vectors scaled so that their dot products with the query sit just below $\theta$, and another whose members oppose the stance but have large dot products because of vector magnitude. If Q-DISCO or Q-Peeling returns the opposing clique, the dot-product agreement model is falsified as a measure of true alignment; a corrected variant should recover the shared-stance clique once opinion vectors are normalized.

Watch

Extended reading notes

Core claim

The central claim is that the query-centric densest subgraph is a natural but hard primitive: maximize $d(S)=|E(S)|/|S|$ subject to $c(S)=\frac{1}{|S|}\sum_{v\in S}\boldsymbol{p}_v\cdot\boldsymbol{q}\ge\theta$. The hardness reduction adds $k$ isolated nodes with agreement $1$ to an instance of the Densest at-Most-$k$-Subgraph problem, so a feasible set mixing original nodes with singletons corresponds exactly to a size-at-most-$k$ solution, giving NP-hardness for binary agreements and, through the known ETH-hardness of Densest $k$-Subgraph, an almost-polynomial approximation barrier. The paper's constructive response is two algorithms with instance-dependent guarantees: Q-Lagrange solves a Lagrangian relaxation by repeatedly invoking a strongly-polynomial algorithm for weighted densest subgraphs with positive and negative node weights, and Q-Peeling peels nodes by the load $\deg_{V'}(v)+z_2(c_v-\theta)$ while binary-searching $z_2$ using the LP dual; each outputs a feasible subgraph and an explicit bound on its gap from optimality. Empirically, the authors report Q-Peeling matches or beats the baselines and finds near-optimal solutions for most queries, and scales to graphs with tens of millions of edges.

Load-bearing premise

The whole method assumes that the dot product between a node's opinion vector and the query vector faithfully captures how much that node agrees with the queried position; if the opinion vectors are noisy, inconsistently scaled, or mixed-stance, a set satisfying $c(S)\ge\theta$ may not actually share the query's stance.

Editorial extensions

If this is right

  • The ETH-hardness result means no polynomial-time algorithm can give a practically acceptable worst-case approximation for Q-DISCO, so the field should focus on heuristics with instance-dependent guarantees or on restricted input classes.
  • Q-Lagrange's a-posteriori bound gives practitioners a certificate: the closer the returned set's average agreement is to the threshold $\theta$, the closer its density is to optimal.
  • Q-Peeling's guarantee is half the optimum minus a penalty proportional to the excess agreement of its last feasible set, so the same certificate logic applies in near-linear time.
  • Raising $\theta$ continuously morphs the output from the graph's densest subgraph into a small, opinion-pure community, giving a controlled trade-off between density and alignment.
  • Both algorithms avoid LP solvers and run in near-linear time times a logarithmic number of iterations, so they scale to graphs with tens of millions of edges where LP-based baselines time out.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because the dot-product agreement is scale-sensitive, normalizing every opinion vector to unit length before forming $c_v$ would make the query semantics invariant to how loudly a user expresses an opinion; this is a direct, testable modification of the model rather than a new algorithm.
  • The hardness reduction from size-constrained densest subgraph suggests that adding any extra linear constraint on the node weights, such as a second topic threshold, is likely to preserve or increase the hardness, and the peeling load $\deg(v)+z_2(c_v-\theta)$ naturally extends by appending more weighted terms.
  • The a-posteriori bounds depend on observable quantities, so a practical deployment could report the gap $c(S_{\rm out})-\theta$ as a live quality indicator and tell a user whether to loosen the threshold.
  • On opinion-labeled social data, running Q-Peeling with a query and its negation, e.g., $+\boldsymbol{q}$ and $-\boldsymbol{q}$, would yield two subgraphs whose sizes and densities quantify the polarization of the network around that axis.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The manuscript introduces Q-DISCO, a query-centric densest-subgraph problem in which each node carries a vector of opinions and the goal is to maximize subgraph density subject to the average dot-product agreement with a query vector being at least a threshold. It proves NP-hardness and ETH-based inapproximability through a reduction from the Densest at-Most-k Subgraph problem, and it proposes two heuristics: Q-Lagrange, based on a Lagrangian relaxation solved via the HDSP-PN algorithm, and Q-Peeling, a greedy peeling method interpreted through the dual of an LP relaxation. Both algorithms are accompanied by a-posteriori approximation guarantees. The empirical section tests the algorithms on Twitter, DBLP, and Deezer, with additional scalability experiments on four SNAP graphs.

Significance. If the claims hold, the paper makes a useful contribution to dense-subgraph discovery: the problem formulation is natural, the hardness results justify the heuristic approach, and the LP-dual interpretation gives a principled basis for the peeling algorithm. The a-posteriori guarantees are honest certificates rather than pre-test predictions, and the code is publicly available. The main weakness is that the real-world validation, especially on Twitter, depends on opinion scores produced by GPT-3.5 without validation against human judgments or an alternative model, and the crawl is explicitly biased by a single seed user; this limits the strength of the 'valuable insights' conclusions.

major comments (2)
  1. [Section B.1, Tables 2-3, Section 5.2] The Twitter opinion vectors are generated solely by GPT-3.5 with no validation against human labels, a second model, or any measure of label agreement, and the network was crawled from a single self-declared Republican seed with strongly negative opinions, as the paper itself acknowledges. Since every algorithm's objective is driven by c_v = p_v · q, a subgraph satisfying c(S) >= theta may be dense only with respect to unvalidated GPT-based scores and may not correspond to a group that genuinely shares the queried stance. Consequently, the claim in the abstract and Section 5.2 that the algorithms 'extract valuable insights' from the Twitter data is not fully supported. Please add validation of the opinion scores (e.g., a human-annotated subsample or a second LLM with agreement statistics), a robustness analysis under noise or systematic bias in the opinion scores, or substantially soften the real-world utility claim.
  2. [Section 5.2, Table 2 and case-study paragraph] There is an internal inconsistency in the description of the Agreement Filtering baseline: the text states that for query q=(1,1) with theta=0.5 the baseline returns an empty set, while Table 2 reports AF with density 0 and agreement 0.72, which suggests a singleton fallback rather than an empty set. Please clarify the exact behavior of AF and make the table and prose consistent.
minor comments (4)
  1. [Appendix A.1] The proof of Proposition 1 phrases the reduction as an 'if and only if' between source and target solutions with the same value val; more precisely, a DamkS solution of density val yields a Q-DISCO solution of density val/2, while a Q-DISCO solution of density val yields a DamkS solution of density at least 2val. The optimal-value correspondence is what the reduction needs, but the current wording is mathematically imprecise and should be corrected.
  2. [Proposition 5 and Appendix A.3] The proof of Proposition 5 states 'Recalling ℓ(T) >= OPT' without restating why this inequality holds; since it is central to the a-posteriori bound, the proof should explicitly note that the dual-feasible solution constructed from the peeling procedure has objective ℓ(T), so ℓ(T) is an upper bound on OPT by weak duality.
  3. [Section B.1] The description of the Twitter dataset would benefit from reporting how many tweets were excluded as irrelevant by GPT-3.5, how the per-user averages are computed when a user has tweets on only one topic, and whether the released dataset will include both the raw tweets and the opinion scores in a way that protects user privacy as claimed in the Ethical Considerations section.
  4. [Table 4] The UB column is described only as an upper bound from Proposition 4; it would be helpful to state explicitly that the same bound is used for both Q-Lagrange and Q-Peeling, since the bound depends on the final Lagrange multiplier and is algorithm-specific.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the hardness reduction, Lagrangian/LP-dual derivations, and a-posteriori bounds are self-contained; self-citations are not load-bearing.

full rationale

After walking the derivation chain, I find no step in which a claimed result is equivalent, by construction, to its own inputs. Proposition 1 (Appendix A.1) reduces DamkS to Q-DISCO by adding k agreement-1 singletons to the original graph and setting theta=1/2; the agreement values are defined directly from the DamkS instance and the claimed density correspondence is explicit, so the hardness conclusion is carried by external results [33, 43] rather than by the paper's own formulation. Proposition 4 is an a-posteriori inequality derived from the output's optimality for the Lagrangian relaxation; it is a certificate, not a fitted prediction, and Proposition 5's dual solution is explicitly constructed from the peeling loads with l(T) as the weak-duality upper bound. Neither algorithm fits a parameter to a subset of data and then reports a closely related quantity as a prediction; the reported UB values are computed from the final lambda or z2 and are valid upper bounds on OPT. The self-citations (e.g., [21] for HDSP, [47] for the DBLP dataset, [58] for the Twitter crawler) appear in related-work, dataset attribution, or tool attribution; none is the unique justification for a theorem or a forced uniqueness claim. The main limitations are empirical: GPT-3.5 opinion scores are not validated against human judgments and the Twitter crawl starts from a single opinionated seed, and the Q-Peeling binary search relies on a non-monotone feasibility heuristic. These are data-quality and robustness concerns, not circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The model has no fitted free parameters; the only tunable quantities are algorithmic search bounds (lambda, z2) and the user-chosen threshold theta. The main load-bearing assumptions are the dot-product agreement model and reliance on prior polynomial algorithms for HDSP-PN. No new entities are postulated, so the invented-entities ledger is empty.

assumptions (4)
  • domain assumption Agreement between a node and a query is the dot product of their opinion vectors, c_v = p_v . q.
    Section 3.1, Problem 1, defines the entire objective and constraint through c_v = p_v . q. If this is not a faithful measure of opinion alignment, the extracted subgraph may not reflect true stance sharing.
  • domain assumption Density |E(S)|/|S| is the appropriate measure of community quality.
    This follows the classical densest subgraph objective and is standard in the literature, but it is a modeling choice that favors large edge counts over other notions of cohesion.
  • domain assumption The algorithm of Huang et al. [29] solves HDSP-PN in strongly-polynomial time.
    Section 4.1 relies on this as a subroutine for Q-Lagrange. The paper does not reproduce or prove this result, and cites the prior work as a black box.
  • standard math LP duality and weak/strong duality for the stated LP (3)-(4).
    Used in Section 4.2 to interpret Q-Peeling as solving a dual LP. This is standard but unproved in the paper, and the precise connection to the peeling objective is where the proof gap appears.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Q-DISCO: Query-Centric Densest Subgraphs in Networks with Opinion Information." pith.science (2026). https://pith.science/paper/4KXNE7Z2

@misc{pith2026241211647,
  author       = {Pith},
  title        = {Pith review of: Q-DISCO: Query-Centric Densest Subgraphs in Networks with Opinion Information},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4KXNE7Z2}},
  note         = {Machine review of arXiv:2412.11647}
}
abstract

Given a network $G=(V,E)$, where each node $v$ is associated with a vector $\boldsymbol{p}_v \in \mathbb{R}^d$ representing its opinion about $d$ different topics, how can we uncover subsets of nodes that not only exhibit exceptionally high density but also possess positively aligned opinions on multiple topics? In this paper we focus on this novel algorithmic question, that is essential in an era where digital social networks are hotbeds of opinion formation and dissemination. We introduce a novel methodology anchored in the well-established densest subgraph problem. We analyze the computational complexity of our formulation, indicating that our problem is NP-hard and eludes practically acceptable approximation guarantees. To navigate these challenges, we design two heuristic algorithms: the first is predicated on the Lagrangian relaxation of our formulation, while the second adopts a peeling algorithm based on the dual of a Linear Programming relaxation. We elucidate the theoretical underpinnings of their performance and validate their utility through empirical evaluation on real-world datasets. Among others, we delve into Twitter datasets we collected concerning timely issues, such as the Ukraine conflict and the discourse surrounding COVID-19 mRNA vaccines, to gauge the effectiveness of our methodology. Our empirical investigations verify that our algorithms are able to extract valuable insights from networks with opinion information.

Figures

Figures reproduced from arXiv: 2412.11647 by the authors.

Figure 1
Figure 1. (a) Demonstration of Q-Lagrange and (b) a bad in￾stance. In the graph in (b), the agreements of nodes 𝑎, 𝑏, and 𝑐 are 1, −0.5, and −0.5, respectively. The agreements of nodes in 𝐾4 are all −1. Let 𝜃 = 0. The linear relations between 𝜆 and 𝐻𝜆 (𝑆) of some representative subsets are shown in (c). While the optimal solution is {𝑎, 𝑏, 𝑐}, the optimal value of 𝐽 (𝜆) is achieved by only 𝐾4 and {𝑎}. Therefore, Q-Lagrange ou… view at source ↗
Figure 2
Figure 2. Histogram of opinions on (Vax, Ukraine) for the (a) full dataset and the outputs of Q-Peeling for 𝜃 = 0.5 with queries (b) 𝒒 = (1, 1), (c) 𝒒 = (1, −1), (d) 𝒒 = (−1, 1), and (e) 𝒒 = (−1, −1). (a) (b) (c) (d) (e) [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Results for the DBLP dataset with adjusting the threshold [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Results for query vector 𝒒P,¬RoDRe. (a) Trade-off between the the average agreement and the density of the output of Q-Peeling as we range 𝜃. (b) The fraction of music fans liking each genre as a function of 𝜃 [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]
Figure 5
Figure 5. Figure 5: Histogram of opinions on (Vax, Ukraine) for the outputs of Q-Peeling for 𝜃 = 1.1 with query 𝒒 = (−1, 1). Tweet Rating Instructions • Return only integer rate for the following tweet. The rate represents its opinion towards COVID vaccination with an integer between 0 to…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

65 extracted references · 61 canonical work pages

  1. [1]

    Tsourakakis

    Rediet Abebe, T-H Hubert Chan, Jon Kleinberg, Zhibin Liang, David Parkes, Mauro Sozio, and Charalampos E. Tsourakakis. 2021. Opinion dynamics opti- mization by varying susceptibility to persuasion via non-convex local search. ACM Transactions on Knowledge Discovery from Data 16, 2 (2021), 1–34

    work page 2021

  2. [2]

    Aris Anagnostopoulos, Luca Becchetti, Adriano Fazzone, Cristina Menghini, and Chris Schwiegelshohn. 2020. Spectral relaxations and fair densest subgraphs. In CIKM ’20. 35–44

    work page 2020

  3. [3]

    Reid Andersen and Kumar Chellapilla. 2009. Finding dense subgraphs with size bounds. In W A W ’09. 25–37

    work page 2009

  4. [4]

    Sanjeev Arora, Elad Hazan, and Satyen Kale. 2012. The multiplicative weights update method: A meta-algorithm and applications. Theory of Computing 8, 1 (2012), 121–164

    work page 2012

  5. [5]

    Bahman Bahmani, Ravi Kumar, and Sergei Vassilvitskii. 2012. Densest subgraph in streaming and MapReduce. In VLDB ’12. 454–465

    work page 2012

  6. [6]

    Eytan Bakshy, Itamar Rosenn, Cameron Marlow, and Lada Adamic. 2012. The role of social networks in information diffusion. In WWW ’12. 519–528

    work page 2012

  7. [7]

    Balalau, Francesco Bonchi, T-H Hubert Chan, Francesco Gullo, and Mauro Sozio

    Oana D. Balalau, Francesco Bonchi, T-H Hubert Chan, Francesco Gullo, and Mauro Sozio. 2015. Finding subgraphs with maximum total density and limited overlap. In WSDM ’15. 379–388

    work page 2015

  8. [8]

    Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, and Aravindan Vijayaraghavan. 2010. Detecting high log-densities: An 𝑂(𝑛1/4) approximation for densest𝑘-subgraph. In STOC ’10. 201–210

    work page 2010

Show all 65 references
  1. [9]

    Tsourakakis

    Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, and Charalam- pos E. Tsourakakis. 2015. Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. In STOC ’15. 173–182

    2015

  2. [10]

    Tsourakakis, Di Wang, and Junxing Wang

    Digvijay Boob, Yu Gao, Richard Peng, Saurabh Sawlani, Charalampos E. Tsourakakis, Di Wang, and Junxing Wang. 2020. Flowless: Extracting dens- est subgraphs without flow computations. In TheWebConf ’20. 573–583

    2020

  3. [11]

    Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press

    2004

  4. [12]

    Brown, Benjamin Mann, Nick Ryder, et al

    Tom B. Brown, Benjamin Mann, Nick Ryder, et al. 2020. Language models are few-shot learners. In NeurIPS ’20. 1877–1901

    2020

  5. [13]

    Moses Charikar. 2000. Greedy approximation algorithms for finding dense components in a graph. In APPROX ’00. 84–95

    2000

  6. [14]

    Chandra Chekuri, Kent Quanrud, and Manuel R. Torres. 2022. Densest subgraph: Supermodularity, iterative peeling, and flow. In SODA ’22. 1531–1555

    2022

  7. [15]

    Tsourakakis

    Tianyi Chen, Brian Matejek, Michael Mitzenmacher, and Charalampos E. Tsourakakis. 2022. Algorithmic tools for understanding the motif structure of networks. In ECML PKDD ’22. 3–19

    2022

  8. [16]

    Tsourakakis

    Tianyi Chen, Xu Wang, and Charalampos E. Tsourakakis. 2022. Polarizing opinion dynamics with confirmation bias. In SocInfo ’22. 144–158

    2022

  9. [17]

    Pranav Dandekar, Ashish Goel, and David T. Lee. 2013. Biased assimilation, ho- mophily, and the dynamics of polarization. Proceedings of the National Academy of Sciences of the United States of America 110, 15 (2013), 5791–5796

    2013

  10. [18]

    Maximilien Danisch, T-H Hubert Chan, and Mauro Sozio. 2017. Large scale density-friendly graph decomposition via convex programming. In WWW ’17. 233–242

    2017

  11. [19]

    Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: Pre-training of deep bidirectional transformers for language understanding. In NAACL-HLT ’19. 4171–4186

    2019

  12. [20]

    Woodruff

    Hossein Esfandiari, MohammadTaghi Hajiaghayi, and David P. Woodruff. 2015. Applications of uniform sampling: Densest subgraph and beyond. arXiv preprint arXiv:1506.04505 (2015)

    2015 arXiv

  13. [21]

    Tsourakakis, and Francesco Bonchi

    Adriano Fazzone, Tommaso Lanciano, Riccardo Denni, Charalampos E. Tsourakakis, and Francesco Bonchi. 2022. Discovering polarization niches via dense subgraphs with attractors and repulsers. In VLDB ’22. 3883–3896

    2022

  14. [22]

    Jason Gaitonde, Jon Kleinberg, and Éva Tardos. 2020. Adversarial perturbations of opinion dynamics in networks. In EC ’20. 471–472

    2020

  15. [23]

    Edoardo Galimberti, Francesco Bonchi, and Francesco Gullo. 2017. Core decom- position and densest subgraph in multilayer networks. In CIKM ’17. 1807–1816

    2017

  16. [24]

    Grigoriadis, and Robert E

    Giorgio Gallo, Michael D. Grigoriadis, and Robert E. Tarjan. 1989. A fast para- metric maximum flow algorithm and applications. SIAM J. Comput. 18, 1 (1989), 30–55

    1989

  17. [25]

    Aristides Gionis, Evimaria Terzi, and Panayiotis Tsaparas. 2013. Opinion maxi- mization in social networks. In SDM ’13. 387–395

    2013

  18. [26]

    Tsourakakis

    Aristides Gionis and Charalampos E. Tsourakakis. 2015. Dense subgraph discov- ery: KDD 2015 Tutorial. In KDD ’15. 2313–2314

    2015

  19. [27]

    Goldberg

    Andrew V. Goldberg. 1984. Finding a maximum density subgraph . Technical Report. University of California Berkeley

    1984

  20. [28]

    Huang and Andrew B

    Dennis J.-H. Huang and Andrew B. Kahng. 1995. When clusters meet partitions: New density-based methods for circuit decomposition. In EDTC ’95. 60–64

    1995

  21. [29]

    Gleich, and Nate Veldt

    Yufan Huang, David F. Gleich, and Nate Veldt. 2024. Densest subhypergraph: Neg- ative supermodular functions and strongly localized methods. InTheWebConf ’24. 881–892

    2024

  22. [30]

    Vinay Jethava and Niko Beerenwinkel. 2015. Finding dense subgraphs in rela- tional graphs. In ECML PKDD ’15. 641–654

    2015

  23. [31]

    Kaplan and Michael Haenlein

    Andreas M. Kaplan and Michael Haenlein. 2010. Users of the world, unite! The challenges and opportunities of social media. Business Horizons 53, 1 (2010), 59–68

    2010

  24. [32]

    Yasushi Kawase, Atsushi Miyauchi, and Hanna Sumita. 2023. Stochastic solutions for dense subgraph discovery in multilayer networks. In WSDM ’23. 886–894

    2023

  25. [33]

    Samir Khuller and Barna Saha. 2009. On finding dense subgraphs. In ICALP ’09. 597–608

    2009

  26. [34]

    Yehuda Koren, Steffen Rendle, and Robert Bell. 2022. Advances in collaborative filtering. In Recommender Systems Handbook , Francesco Ricci, Lior Rokach, and Bracha Shapira (Eds.). Springer US, 91–142

    2022

  27. [35]

    Guy Kortsarz and Zeev Nutov. 2005. Approximating𝑘-node connected subgraphs via critical graphs. SIAM J. Comput. 35, 1 (2005), 247–257

    2005

  28. [36]

    Yuko Kuroki, Atsushi Miyauchi, Junya Honda, and Masashi Sugiyama. 2020. Online dense subgraph discovery via blurred-graph feedback. In ICML ’20. 5522– 5532

    2020

  29. [37]

    Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue Moon. 2010. What is Twitter, a social network or a news media?. InWWW ’10. 591–600

    2010

  30. [38]

    Tommaso Lanciano, Atsushi Miyauchi, Adriano Fazzone, and Francesco Bonchi

  31. [39]

    Theodoros Lappas, Kun Liu, and Evimaria Terzi. 2009. Finding a team of experts in social networks. In KDD ’09. 467–476

    2009

  32. [40]

    Lee, Ning Ruan, Ruoming Jin, and Charu Aggarwal

    Victor E. Lee, Ning Ruan, Ruoming Jin, and Charu Aggarwal. 2010. A survey of algorithms for dense subgraph discovery. In Managing and Mining Graph Data , Charu C. Aggarwal and Haixun Wang (Eds.). Springer US, 303–336

    2010

  33. [41]

    Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http://snap.stanford.edu/data

    2014

  34. [42]

    Lakshmanan, Wenjie Zhang, and Xuemin Lin

    Chenhao Ma, Yixiang Fang, Reynold Cheng, Laks V.S. Lakshmanan, Wenjie Zhang, and Xuemin Lin. 2020. Efficient algorithms for densest subgraph discovery on large directed graphs. In SIGMOD ’20. 1051–1066

    2020

  35. [43]

    Pasin Manurangsi. 2017. Almost-polynomial ratio ETH-hardness of approximat- ing densest𝑘-subgraph. In STOC ’17. 954–961

    2017

  36. [44]

    Andrew McGregor, David Tench, Sofya Vorotnikova, and Hoa T. Vu. 2015. Dens- est subgraph in dynamic graph streams. In MFCS ’15. 472–482

    2015

  37. [45]

    Isaac D Mehlhaff. 2024. A group-based approach to measuring polarization. American Political Science Review 118, 3 (2024), 1518–1526

    2024

  38. [46]

    Tsourakakis, and Shen Chen Xu

    Michael Mitzenmacher, Jakub Pachocki, Richard Peng, Charalampos E. Tsourakakis, and Shen Chen Xu. 2015. Scalable large near-clique detection in large-scale networks via sampling. In KDD ’15. 815–824

    2015

  39. [47]

    Tsourakakis

    Atsushi Miyauchi, Tianyi Chen, Konstantinos Sotiropoulos, and Charalampos E. Tsourakakis. 2023. Densest diverse subgraphs: How to plan a successful cocktail party with diversity. In KDD ’23. 1710–1721

    2023

  40. [48]

    Atsushi Miyauchi and Naonori Kakimura. 2018. Finding a dense subgraph with sparse cut. In CIKM ’18. 547–556

    2018

  41. [49]

    Atsushi Miyauchi and Akiko Takeda. 2018. Robust densest subgraph discovery. In ICDM ’18. 1188–1193

    2018

  42. [50]

    Tsourakakis

    Cameron Musco, Christopher Musco, and Charalampos E. Tsourakakis. 2018. Minimizing polarization and disagreement in social networks. InTheWebConf ’18. 369–378

    2018

  43. [51]

    Tsourakakis, and Panagiotis Karras

    Petros Petsinis, Charalampos E. Tsourakakis, and Panagiotis Karras. 2024. Finding dense and persistently expansive subgraphs. In TheWebConf ’24. 553–556

    2024

  44. [52]

    Jean-Claude Picard and Maurice Queyranne. 1982. A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory. Networks 12, 2 (1982), 141–159. Chen, Miyauchi, Tsourakakis

    1982

  45. [53]

    Polyvios Pratikakis. 2018. twAwler: A lightweight twitter crawler. arXiv preprint arXiv:1804.07748 (2018)

    2018 arXiv

  46. [54]

    Proskurnikov and Roberto Tempo

    Anton V. Proskurnikov and Roberto Tempo. 2017. A tutorial on modeling and analysis of dynamic social networks. Part I. Annual Reviews in Control 43 (2017), 65–79

    2017

  47. [55]

    Proskurnikov and Roberto Tempo

    Anton V. Proskurnikov and Roberto Tempo. 2018. A tutorial on modeling and analysis of dynamic social networks. Part II. Annual Reviews in Control 45 (2018), 166–190

    2018

  48. [56]

    Tsourakakis

    Dragos Ristache, Fabian Spaeh, and Charalampos E. Tsourakakis. 2024. Wiser than the wisest of crowds: The Asch effect and polarization revisited. In ECML PKDD ’24. 440–458

    2024

  49. [57]

    Benedek Rozemberczki, Ryan Davies, Rik Sarkar, and Charles Sutton. 2019. GEM- SEC: Graph embedding with self clustering. In ASONAM ’19. 65–72

    2019

  50. [58]

    Byers, Polyvios Pratikakis, and Charalam- pos E

    Konstantinos Sotiropoulos, John W. Byers, Polyvios Pratikakis, and Charalam- pos E. Tsourakakis. 2019. TwitterMancer: Predicting user interactions on Twitter. In Allerton ’19. 973–980

    2019

  51. [59]

    Bintao Sun, Maximilien Danisch, T-H Hubert Chan, and Mauro Sozio. 2020. KClist++: A simple algorithm for finding k-clique densest subgraphs in large graphs. In VLDB ’20. 1628–1640

    2020

  52. [60]

    Tsourakakis

    Charalampos E. Tsourakakis. 2015. The k-clique densest subgraph problem. In WWW ’15. 1122–1132

    2015

  53. [61]

    Tsourakakis, Francesco Bonchi, Aristides Gionis, Francesco Gullo, and Maria Tsiarli

    Charalampos E. Tsourakakis, Francesco Bonchi, Aristides Gionis, Francesco Gullo, and Maria Tsiarli. 2013. Denser than the densest subgraph: Extracting optimal quasi-cliques with quality guarantees. In KDD ’13. 104–112

    2013

  54. [62]

    Tsourakakis, Tianyi Chen, Naonori Kakimura, and Jakub Pa- chocki

    Charalampos E. Tsourakakis, Tianyi Chen, Naonori Kakimura, and Jakub Pa- chocki. 2019. Novel dense subgraph discovery primitives: Risk aversion and exclusion queries. In ECML PKDD ’19. 378–394

    2019

  55. [63]

    Benson, and Jon Kleinberg

    Nate Veldt, Austin R. Benson, and Jon Kleinberg. 2021. The generalized mean densest subgraph problem. In KDD ’21. 1604–1614

    2021

  56. [64]

    Wenxuan Zhang, Yue Deng, Bing Liu, Sinno Pan, and Lidong Bing. 2024. Senti- ment analysis in the era of large language models: A reality check. In Findings of the Association for Computational Linguistics: NAACL ’24 . 3881–3906. Q-DISCO: Query-Centric Densest Subgraphs in Netw...

    2024

  57. [2024]

    A survey on the densest subgraph problem and its variants. Comput. Surveys 56, 8 (2024), 1–40

    2024

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.