Keyword-based Community Search in Bipartite Spatial-Social Networks (Technical Report)
Pith reviewed 2026-05-15 17:16 UTC · model grok-4.3
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.
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 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
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.
Referee Report
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)
- [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.
- [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.
- [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.
- [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)
- [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
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
-
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
-
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
-
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
-
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
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
free parameters (2)
- ω
- π
axioms (1)
- standard math Bipartite graphs consist of two disjoint node sets with edges only between the sets.
invented entities (1)
-
(ω, π)-keyword-core
no independent evidence
Reference graph
Works this paper leans on
-
[1]
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
work page 2006
-
[2]
A. Al-Baghdadi and X. Lian. Topic-based community search over spatial-social networks.Proc. VLDB Endow., 13(12):2104–2117, jul 2020
work page 2020
-
[3]
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
work page 2022
-
[4]
N. Barbieri, F. Bonchi, and G. Manco. Topic-aware social influence propagation models.Knowledge and information systems, 37(3):555–584, 2013
work page 2013
-
[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]
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
work page 2024
-
[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
work page 2015
-
[8]
J. Cohen. Trusses: Cohesive subgraphs for social network analysis.National security agency technical report, 16(3.1), 2008
work page 2008
-
[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
work page 2017
-
[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
work page 2020
-
[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
work page 2093
-
[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
work page 2020
-
[13]
K. R. Gabriel and R. R. Sokal. A New Statistical Approach to Geographic Variation Analysis.Systematic Biology, 18(3):259–278, 09 1969
work page 1969
-
[14]
Gibbons.Algorithmic graph theory
A. Gibbons.Algorithmic graph theory. Cambridge university press, 1985
work page 1985
-
[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
work page 2021
-
[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
work page 2024
-
[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
work page 2023
-
[18]
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
work page 2014
-
[19]
X. Huang and L. V. S. Lakshmanan. Attribute-driven community search.Proc. VLDB Endow., 10(9):949–960, may 2017
work page 2017
-
[20]
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
work page 2012
-
[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
work page 2005
-
[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
work page 2024
-
[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
work page 2024
- [24]
-
[25]
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
work page 2003
-
[26]
S. B. Seidman. Network structure and minimum degree.Social Networks, 5(3):269– 287, 1983
work page 1983
-
[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
work page 2011
-
[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
work page 2006
-
[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
work page 2022
-
[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
work page 2021
-
[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
work page 2023
-
[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
work page 2024
-
[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
work page 2022
-
[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
work page 2025
-
[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
work page 2023
-
[36]
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
work page 2012
-
[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
work page 2017
-
[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
work page 2018
- [39]
-
[40]
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
work page 2019
-
[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
work page 2023
-
[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
work page 2025
-
[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...
work page 2047
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.