pith. sign in

arxiv: 2603.01500 · v3 · submitted 2026-03-02 · 💻 cs.SI

Keyword-based Community Search in Bipartite Spatial-Social Networks (Technical Report)

Pith reviewed 2026-05-15 17:16 UTC · model grok-4.3

classification 💻 cs.SI
keywords community searchbipartite networksspatial-social networkskeyword corepruning methodsindexing techniquequery efficiency
0
0 comments X

The pith

Keyword-based community search in bipartite spatial-social networks uses pruning and indexing to find tight groups with keyword cores, high influence, and minimal travel distances.

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

The paper establishes a new community search problem called KCS-BSSN in bipartite spatial-social networks. It seeks communities containing a query user that include a (ω, π)-keyword-core, possess significant social influence, form tight connections, and minimize travel distances to points of interest. Pruning methods are developed to filter irrelevant users and points of interest, and a bipartite-spatial-social index is proposed to accelerate query answering. These approaches are validated as effective and efficient via experiments on real and artificial datasets. A reader would care if they need to identify relevant social groups in location-aware networks for applications like event planning or targeted recommendations.

Core claim

The paper claims that the KCS-BSSN problem can be solved by defining communities around the (ω, π)-keyword-core that are tightly-knit, socially influential, and spatially efficient, achieved through novel pruning techniques and the bipartite-spatial-social index, with experimental confirmation on various datasets.

What carries the argument

The (ω, π)-keyword-core combined with pruning methods that remove irrelevant users and points of interest, and the bipartite-spatial-social index for query efficiency.

If this is right

  • The method efficiently identifies communities without examining all possible nodes.
  • Query answering becomes faster due to the specialized index structure.
  • Communities balance social influence and spatial proximity effectively.
  • Performance holds for both real-world and synthetic bipartite spatial-social networks.

Where Pith is reading between the lines

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

  • These techniques might extend to other types of bipartite networks beyond spatial-social ones.
  • Integration with real-time location data could enable dynamic community recommendations.
  • Further work could explore how the keyword core parameters affect community quality in different domains.

Load-bearing premise

The pruning methods and indexing technique will maintain their effectiveness and efficiency across all types of real-world bipartite spatial-social networks, not just the tested ones.

What would settle it

A test on a large, previously unseen bipartite spatial-social network where the pruning fails to reduce the search space adequately or the index does not improve query times would falsify the efficiency claims.

Figures

Figures reproduced from arXiv: 2603.01500 by Kovan A. Bavi, Xiang Lian.

Figure 1
Figure 1. Figure 1: An example of bipartite spatial-social networks. To address this gap, we introduce a new community search problem, namely Keyword-based Community Search in Bipartite Spatial-Social Networks (𝐾𝐶𝑆-𝐵𝑆𝑆𝑁). The objective of 𝐾𝐶𝑆-𝐵𝑆𝑆𝑁 is to retrieve a cohesive community that: (1) contains a query user 𝑞, (2) satisfies strong structural cohesiveness in the social network, (3) exhibits significant social influence,… view at source ↗
Figure 3
Figure 3. Figure 3: The 𝐾𝐶𝑆-𝐵𝑆𝑆𝑁 offline time vs. real/synthetic graph datasets. Epin Twit DBLP Real Datasets 10 1 10 0 10 1 10 2 10 3 Peak CPU time (ms) KCS-BSSN Baseline (a) real-world graphs Unif Gaus Skew Synthetic Datasets 10 1 10 0 10 1 10 2 10 3 Peak CPU time (ms) KCS-BSSN Baseline (b) synthetic graphs [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The𝐾𝐶𝑆-𝐵𝑆𝑆𝑁 performance vs. real/synthetic graph datasets. approach with a baseline method. In the baseline, five subgraphs within social distance 𝑑 from the query user 𝑞 are sampled, and the total CPU cost is estimated by multiplying their average runtime by the total number of possible subgraphs within distance 𝑑 in 𝐺𝑠 . In each experiment, we vary one parameter while fixing the others to their default v… view at source ↗
Figure 5
Figure 5. Figure 5: Overall 𝐾𝐶𝑆-𝐵𝑆𝑆𝑁 performance comparison for different parameter settings. 0 1 2 3 4 5 6 7 Number of pruning applied 10 1 10 1 10 3 10 5 Number of candidate users Epin Twit DBLP (a) real-world graphs 0 1 2 3 4 5 6 7 Number of pruning applied 10 1 10 1 10 3 10 5 Number of candidate users Unif Gaus Skew (b) synthetic graphs [PITH_FULL_IMAGE:figures/full_fig_p014_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The ablation study of our 𝐾𝐶𝑆-𝐵𝑆𝑆𝑁 pruning strategies on real/synthetic graphs, in terms of the pruning power. performance spikes. Performance vs. Influence Score Threshold 𝜃 [PITH_FULL_IMAGE:figures/full_fig_p014_6.png] view at source ↗
Figure 8
Figure 8. Figure 8: The 𝐾𝐶𝑆-𝑇 𝐵𝑆𝑆𝑁 performance of temporal dynamic updates (deletion) vs. real (𝑇𝑤𝑖𝑡) and synthetic (𝑈 𝑛𝑖 𝑓 ) graphs. parameters held at default settings. The results reveal distinct perfor￾mance trends across the maintenance categories. In the real graph (𝑇𝑤𝑖𝑡), as shown in [PITH_FULL_IMAGE:figures/full_fig_p015_8.png] view at source ↗
read the original abstract

Several approaches have been recently proposed for community search in bipartite graphs. These methods have shown promising results in identifying communities in real-world bipartite networks, such as social and biological networks. Given a query user $q$, community search in bipartite graphs involves identifying a group of users containing $q$, with common characteristics or functions within a given bipartite graph. These problems are particularly challenging because bipartite graphs have two distinct sets of nodes, and community search algorithms must account for this structure. However, finding communities in keyword-based bipartite spatial-social networks has yet to be investigated enough. The spatial-social networks are naturally structured as bipartite graphs. Thus, this paper proposes a new community search problem in Bipartite spatial-social networks with a novel $(\omega, \pi)\mbox{-}keyword\mbox{-}core$, named Keyword-based Community Search in Bipartite Spatial-Social Networks ($KCS\mbox{-}BSSN$). The $KCS\mbox{-}BSSN$ returns a tightly-knit community, significant social influence, minimal travel distance, and includes a $(\omega, \pi)\mbox{-}keyword\mbox{-}core$. To address the $KCS\mbox{-}BSSN$ problem, we have developed pruning methods that effectively filter out irrelevant users and points of interest. To improve query-answering efficiency, we have also proposed an indexing technique named the bipartite-spatial-social index. Our pruning techniques, and indexing approach, have proven effective and efficient through experiments with real and artificial data sets.

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

4 major / 1 minor

Summary. The paper introduces the KCS-BSSN problem for finding communities containing a query user q that form a novel (ω, π)-keyword-core with high social influence and low travel distance in bipartite spatial-social networks. It proposes pruning methods to filter irrelevant users and POIs plus a bipartite-spatial-social index for efficient query processing, asserting that both are effective and efficient based on experiments with real and artificial datasets.

Significance. If the pruning rules prove sound (never discarding valid cores) and the index yields scalable speed-ups with formal backing, the work would fill a gap in community search by jointly handling bipartite structure, spatial distances, social influence, and keywords. The parameter-free framing of the core and the index construction are potentially reusable strengths, but the absence of proofs or detailed empirical support makes the significance hard to gauge at present.

major comments (4)
  1. [Abstract] Abstract: the assertion that 'pruning techniques and indexing approach have proven effective and efficient' is unsupported; no quantitative metrics, baseline comparisons, error bars, runtime tables, or even a high-level description of the pruning conditions appear.
  2. [Methods] Methods / pruning rules: the soundness claim (pruning never removes a valid (ω, π)-keyword-core) is load-bearing for both correctness and the reported speed-ups, yet no formal invariant, proof sketch, or even pseudocode of the pruning predicates is supplied.
  3. [Experiments] Experiments: the central efficiency claim rests on 'real and artificial data sets' with no reported dataset sizes, density statistics, keyword distributions, baseline algorithms, or scaling plots; this prevents assessment of whether the observed gains generalize or are artifacts of the chosen instances.
  4. [Theoretical Analysis] Theoretical analysis: no asymptotic complexity bound, worst-case guarantee, or proof of completeness for the index is given; performance is asserted only empirically on the tested graphs, leaving open the risk that pruning assumptions fail on other bipartite spatial-social networks.
minor comments (1)
  1. [Introduction] The notation (ω, π)-keyword-core is introduced without an explicit mathematical definition in the provided abstract; a clear set of equations would improve readability.

Simulated Author's Rebuttal

4 responses · 0 unresolved

We thank the referee for the constructive and detailed feedback. We agree that the current manuscript requires substantial additions to support its claims on pruning soundness, experimental rigor, and theoretical guarantees. We will revise the paper to address each point.

read point-by-point responses
  1. Referee: [Abstract] Abstract: the assertion that 'pruning techniques and indexing approach have proven effective and efficient' is unsupported; no quantitative metrics, baseline comparisons, error bars, runtime tables, or even a high-level description of the pruning conditions appear.

    Authors: We acknowledge that the abstract overstates the experimental support without sufficient detail. In the revision we will replace the vague claim with concrete quantitative results (e.g., average speed-up factors and accuracy metrics) drawn from the experiments section and will add a one-sentence high-level description of the pruning conditions. revision: yes

  2. Referee: [Methods] Methods / pruning rules: the soundness claim (pruning never removes a valid (ω, π)-keyword-core) is load-bearing for both correctness and the reported speed-ups, yet no formal invariant, proof sketch, or even pseudocode of the pruning predicates is supplied.

    Authors: We agree that a formal argument is required. The revised manuscript will include a proof sketch establishing the invariant that the pruning rules never discard a valid (ω, π)-keyword-core, together with pseudocode for each pruning predicate. revision: yes

  3. Referee: [Experiments] Experiments: the central efficiency claim rests on 'real and artificial data sets' with no reported dataset sizes, density statistics, keyword distributions, baseline algorithms, or scaling plots; this prevents assessment of whether the observed gains generalize or are artifacts of the chosen instances.

    Authors: The full manuscript contains basic dataset descriptions, but we accept that they are insufficiently detailed. We will expand the experiments section with exact sizes, density and keyword-distribution statistics, explicit baseline descriptions, and scaling plots across varying graph sizes. revision: yes

  4. Referee: [Theoretical Analysis] Theoretical analysis: no asymptotic complexity bound, worst-case guarantee, or proof of completeness for the index is given; performance is asserted only empirically on the tested graphs, leaving open the risk that pruning assumptions fail on other bipartite spatial-social networks.

    Authors: We will add a dedicated theoretical-analysis subsection that supplies asymptotic complexity bounds for index construction and query answering, a completeness argument for the index, and a discussion of the conditions under which the pruning rules remain valid. revision: yes

Circularity Check

0 steps flagged

No circularity: new problem definition, pruning rules, and index are independent contributions validated empirically

full rationale

The paper defines a new problem KCS-BSSN along with the (ω, π)-keyword-core concept, then introduces pruning methods and a bipartite-spatial-social index as algorithmic contributions. Effectiveness is asserted solely via experiments on real and synthetic datasets. No equations, derivations, or self-citations appear that reduce any claimed result to a fitted parameter, self-referential definition, or prior author work by construction. The derivation chain is therefore self-contained and does not collapse to its inputs.

Axiom & Free-Parameter Ledger

2 free parameters · 1 axioms · 1 invented entities

The central claim rests on the newly introduced (ω, π)-keyword-core definition, the correctness of the pruning rules, and the performance of the bipartite-spatial-social index; these are presented as original without reference to independently validated external benchmarks.

free parameters (2)
  • ω
    Threshold parameter inside the (ω, π)-keyword-core definition that controls keyword overlap requirements.
  • π
    Threshold parameter inside the (ω, π)-keyword-core definition that controls structural or influence requirements.
axioms (1)
  • standard math Bipartite graphs consist of two disjoint node sets with edges only between the sets.
    Invoked when the problem is defined on spatial-social networks modeled as bipartite graphs.
invented entities (1)
  • (ω, π)-keyword-core no independent evidence
    purpose: To enforce both keyword sharing and structural tightness inside the returned community.
    New core concept introduced to capture the desired community properties; no independent evidence outside the paper is provided.

pith-pipeline@v0.9.0 · 5571 in / 1451 out tokens · 41066 ms · 2026-05-15T17:16:15.877425+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

43 extracted references · 43 canonical work pages

  1. [1]

    Acquisti and R

    A. Acquisti and R. Gross. Imagined communities: Awareness, information sharing, and privacy on the facebook. InInternational workshop on privacy enhancing technologies, pages 36–58. Springer, 2006

  2. [2]

    Al-Baghdadi and X

    A. Al-Baghdadi and X. Lian. Topic-based community search over spatial-social networks.Proc. VLDB Endow., 13(12):2104–2117, jul 2020

  3. [3]

    Al-Baghdadi, G

    A. Al-Baghdadi, G. Sharma, and X. Lian. Efficient processing of group planning queries over spatial-social networks.IEEE Transactions on Knowledge and Data Engineering, 34(5):2135–2147, 2022

  4. [4]

    Barbieri, F

    N. Barbieri, F. Bonchi, and G. Manco. Topic-aware social influence propagation models.Knowledge and information systems, 37(3):555–584, 2013

  5. [5]

    An o(m) algorithm for cores decomposition of networks

    V. Batagelj and M. Zaversnik. An o(m) algorithm for cores decomposition of networks.CoRR, cs.DS/0310049, 2003

  6. [6]

    G. Chen, F. Guo, Y. Wang, Y. Liu, P. Yu, H. Shen, and X. Cheng. Fcs-hgnn: Flexible multi-type community search in heterogeneous information networks. InProceedings of the 33rd ACM International Conference on Information and Knowledge Management, CIKM ’24, page 207–217, New York, NY, USA, 2024. Association for Computing Machinery

  7. [7]

    S. Chen, J. Fan, G. Li, J. Feng, K.-l. Tan, and J. Tang. Online topic-aware influence maximization.Proceedings of the VLDB Endowment, 8(6):666–677, 2015

  8. [8]

    J. Cohen. Trusses: Cohesive subgraphs for social network analysis.National security agency technical report, 16(3.1), 2008

  9. [9]

    D. Ding, H. Li, Z. Huang, and N. Mamoulis. Efficient fault-tolerant group recommendation using alpha-beta-core. InProceedings of the 2017 ACM on Conference on Information and Knowledge Management, CIKM ’17, page 2047–2050, New York, NY, USA, 2017. Association for Computing Machinery

  10. [10]

    Y. Fang, X. Huang, L. Qin, Y. Zhang, W. Zhang, R. Cheng, and X. Lin. A survey of community search over big graphs.The VLDB Journal, 29(1):353–392, 2020

  11. [11]

    Y. Fang, Z. Wang, R. Cheng, H. Wang, and J. Hu. Effective and efficient community search over large directed graphs.IEEE Transactions on Knowledge and Data Engineering, 31(11):2093–2107, 2019

  12. [12]

    Y. Fang, Y. Yang, W. Zhang, X. Lin, and X. Cao. Effective and efficient community search over large heterogeneous information networks.Proc. VLDB Endow., 13(6):854–867, Feb. 2020

  13. [13]

    K. R. Gabriel and R. R. Sokal. A New Statistical Approach to Geographic Variation Analysis.Systematic Biology, 18(3):259–278, 09 1969

  14. [14]

    Gibbons.Algorithmic graph theory

    A. Gibbons.Algorithmic graph theory. Cambridge university press, 1985

  15. [15]

    F. Guo, Y. Yuan, G. Wang, X. Zhao, and H. Sun. Multi-attributed Community Search in Road-social Networks . In2021 IEEE 37th International Conference on Data Engineering (ICDE), pages 109–120, Los Alamitos, CA, USA, Apr. 2021. IEEE Computer Society

  16. [16]

    N. A. H. Haldar, J. Li, N. Akhtar, Y. Jia, and A. Mian. Co-engaged location group search in location-based social networks.IEEE Transactions on Knowledge and Data Engineering, 36(7):2910–2926, 2024

  17. [17]

    N. A. H. Haldar, J. Li, M. E. Ali, T. Cai, Y. Chen, T. Sellis, and M. Reynolds. Top-k socio-spatial co-engaged location selection for social users.IEEE Transactions on Knowledge and Data Engineering, 35(5):5325–5340, 2023

  18. [18]

    Huang, H

    X. Huang, H. Cheng, L. Qin, W. Tian, and J. X. Yu. Querying k-truss community in large and dynamic graphs. InProceedings of the 2014 ACM SIGMOD International Conference on Management of Data, SIGMOD ’14, page 1311–1322, New York, NY, USA, 2014. Association for Computing Machinery

  19. [19]

    Huang and L

    X. Huang and L. V. S. Lakshmanan. Attribute-driven community search.Proc. VLDB Endow., 10(9):949–960, may 2017

  20. [20]

    Leskovec and J

    J. Leskovec and J. Mcauley. Learning to discover social circles in ego networks. In F. Pereira, C. Burges, L. Bottou, and K. Weinberger, editors,Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012

  21. [21]

    F. Li, D. Cheng, M. Hadjieleftheriou, G. Kollios, and S.-H. Teng. On trip planning queries in spatial databases. In C. Bauzer Medeiros, M. J. Egenhofer, and E. Bertino, editors,Advances in Spatial and Temporal Databases, pages 273–290, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg

  22. [22]

    M. Li, R. Borovica-Gajic, F. M. Choudhury, N. Cui, and L. Ding. Maximal size constraint community search over bipartite graphs.Knowledge-Based Systems, 297:111961, 2024

  23. [23]

    S. Li, K. Wang, X. Lin, W. Zhang, Y. He, and L. Yuan. Querying historical cohesive subgraphs over temporal bipartite graphs. In2024 IEEE 40th International Conference on Data Engineering (ICDE), pages 2503–2516, 2024

  24. [24]

    Rai and X

    N. Rai and X. Lian. Top- 𝑘 community similarity search over large-scale road networks.IEEE Transactions on Knowledge and Data Engineering, 35(10):10710– 10721, 2023

  25. [25]

    Richardson, R

    M. Richardson, R. Agrawal, and P. Domingos. Trust management for the semantic web. In D. Fensel, K. Sycara, and J. Mylopoulos, editors,The Semantic Web - ISWC 2003, pages 351–368, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg

  26. [26]

    S. B. Seidman. Network structure and minimum degree.Social Networks, 5(3):269– 287, 1983

  27. [27]

    Y. Sun, J. Han, X. Yan, P. S. Yu, and T. Wu. Pathsim: meta path-based top-k similarity search in heterogeneous information networks.Proc. VLDB Endow., 4(11):992–1003, Aug. 2011

  28. [28]

    J. Wang, A. P. de Vries, and M. J. T. Reinders. Unifying user-based and item-based collaborative filtering approaches by similarity fusion. InProceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR ’06, page 501–508, New York, NY, USA, 2006. Association for Computing Machinery

  29. [29]

    K. Wang, S. Wang, X. Cao, and L. Qin. Efficient radius-bounded community search in geo-social networks.IEEE Transactions on Knowledge and Data Engineering, 34(9):4186–4200, 2022

  30. [30]

    K. Wang, W. Zhang, X. Lin, Y. Zhang, L. Qin, and Y. Zhang. Efficient and effective community search on large-scale bipartite graphs. In2021 IEEE 37th International Conference on Data Engineering (ICDE), pages 85–96, 2021

  31. [31]

    Y. Wang, J. Liu, X. Xu, X. Ke, T. Wu, and X. Gou. Efficient and effective academic expert finding on heterogeneous graphs through (k, 𝑝)-core based embedding. ACM Trans. Knowl. Discov. Data, 17(6), Mar. 2023

  32. [32]

    Y. Wang, S. Ye, X. Xu, Y. Geng, Z. Zhao, X. Ke, and T. Wu. Scalable Community Search with Accuracy Guarantee on Attributed Graphs . In2024 IEEE 40th International Conference on Data Engineering (ICDE), pages 2737–2750, Los Alamitos, CA, USA, May 2024. IEEE Computer Society

  33. [33]

    Z. Wu, J. Xu, H. Zhang, Q. Bao, Qingsun, and Changbengzhou. A progressive approach for neighboring geosocial communities search over large spatial graphs. IEEE Access, 10:57012–57024, 2022

  34. [34]

    H. Xie, Q. Liu, C. Luo, Y. Zhou, and Y. Gao. Truss-based why-not community search. InProceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2, KDD ’25, page 3309–3320, New York, NY, USA, 2025. Association for Computing Machinery

  35. [35]

    Z. Xu, Y. Zhang, L. Yuan, Y. Qian, Z. Chen, M. Zhou, Q. Mao, and W. Pan. Effective community search on large attributed bipartite graphs.International Journal of Pattern Recognition and Artificial Intelligence, 37(02):2359002, 2023

  36. [36]

    Yang and J

    J. Yang and J. Leskovec. Defining and evaluating network communities based on ground-truth. InProceedings of the ACM SIGKDD Workshop on Mining Data Semantics, MDS ’12, New York, NY, USA, 2012. Association for Computing Machinery

  37. [37]

    L. Yuan, L. Qin, X. Lin, L. Chang, and W. Zhang. I/o efficient ecc graph decomposition via graph reduction.The VLDB Journal, 26(2):275–300, Apr. 2017

  38. [38]

    L. Yuan, L. Qin, W. Zhang, L. Chang, and J. Yang. Index-based densest clique percolation community search in networks.IEEE Transactions on Knowledge and 16 Data Engineering, 30(5):922–935, 2018

  39. [39]

    Zhang, Z

    Y. Zhang, Z. Hua, L. Yuan, and Z. Chen. Top-r influential community search in bipartite graphs. InVLDB 2025 Workshop on Large Scale Graph Data Analytics (LSGDA), 2025

  40. [40]

    Zhang and J

    Y. Zhang and J. X. Yu. Unboundedness and efficiency of truss maintenance in evolving graphs. InProceedings of the 2019 International Conference on Management of Data, SIGMOD ’19, page 1024–1041, New York, NY, USA, 2019. Association for Computing Machinery

  41. [41]

    K. Zhou, J. Xin, J. Chen, X. Zhang, B. Wang, and Z. Wang. Effective and efficient community search with size constraint on bipartite graphs.Inf. Sci., 647(C), Nov. 2023

  42. [42]

    L. Zhou, J. Wang, Y. Song, L. Wang, and H. Chen. Community search over heterogeneous information networks: A survey.ACM Comput. Surv., 58(4), Oct. 2025

  43. [43]

    Y. Zhou, Y. Fang, W. Luo, and Y. Ye. Influential community search over large heterogeneous information networks.Proc. VLDB Endow., 16(8):2047–2060, Apr. 2023. A THE PROOFS Proof of the Lemma 1 Proof. From our lemma assumption, if𝑝.𝐾∩𝑄=∅ holds for all POIs 𝑝∈𝑉 𝑝 that user 𝑢 visited, then, for any vertex subset, 𝑉 ′ 𝑝 , of 𝑉𝑝 in a community (subgraph) of gr...