# Cohesive Subgraph Identification in Weighted Bipartite Graphs
## 1 Introduction
* Fraud detection: For an online shopping website, fraudsters use a larger number of accounts to frequently purchase some selected products in order to boost the ranking of these products. This behavior can be modeled with a \((k,\omega)\)-core. By carefully selecting the parameters, we can use the detected \((k,\omega)\)-core to narrow down the searching space of fraudster accounts. In real-life applications, the value of \(k\) (resp. \(\omega\)) is determined by users based on their own requirements. The two parameters provide more flexibility when adjusting the resulting communities. As observed, the \((\alpha,\beta)\)-core is a special case of the \((k,\omega)\)-core when all the weights in the graph equal 1. Naively, we can extend the solution of computing \((\alpha,\beta)\)-core by iteratively deleting the nodes violating the constraints. The time complexity is linear to the input graph. However, in real applications, the graph size is usually large, which means algorithms that are linear to the input graph size are also not affordable [14]. In addition, different users may have different requirements of the input parameters \(k\) and \(\omega\), which can lead to a large amount of queries. Therefore, more efficient methods are expected to handle the massive graphs and queries. In this paper, we resort to index-based approaches. A straightforward solution is to compute all possible \((k,\omega)\)-cores and maintain all the results. However, it will cause a huge computational cost by visiting the same subgraph multiple times. Thus, the time cost of computing all \((k,\omega)\)-cores becomes unaffordable on large graphs. To reduce the cost, we propose different index construction strategies to ensure a balance between building space-efficient indexes and supporting efficient-scalable query processing. Our major contributions are summarized as follows:  
* We propose a new cohesive subgraph model \((k,\omega)\)-core on weighted bipartite graphs by considering both density and frequency of the subgraph. Figure 1: A weighted bipartite graph of the customer–product network (the weight on the edge denotes the number of times that the customer has bought the product). To efficiently handle massive graphs and queries, we develop three advanced index construction strategies, i.e., RowIndex, OptionIndex and UnionIndex, to reduce index construction cost. In addition, the corresponding querying algorithms by using the three index structures are provided. * We validate the advantages of the proposed algorithms through extensive experiments on real-world datasets. The results show that the index-based algorithms outperform the baselines significantly. Moreover, users can make a trade-off between the time and space cost when selecting from the three strategies. Roadmap: The rest of the paper is organized as follows. In Section 2, we introduce the \((k,\omega)\)-core model and formulate our problem. Section 3 introduces the naive online algorithm. Section 4 presents the index-based algorithms and advanced index structures. We report our experimental results in Section 5 and review the related work in Section 6. Finally, we present the conclusion and future work in Section 7.