# Cohesive Subgraph Identification in Weighted Bipartite Graphs
## 1 Introduction  
Bipartite graphs are widely used in many real-world applications to model the complex relationships across different types of entities, such as customer-product network and author-paper collaboration network [1, 2, 3, 4]. A bipartite graph \(G=(L,R,E)\) consists of two sets of disjoint nodes, i.e., \(L\) and \(R\). Only nodes from different sets can be connected. For example, Figure 1 shows an example of customer-product bipartite network, where edges represent the purchase relationships. The left layer \(L\) is a set of customers and the right layer \(R\) consists of a set of products purchased. There is no edge between the customers \(L\) (resp. products \(R\)). As a fundamental problem in graph analysis, cohesive subgraph identification is widely studied in the literature (e.g., [5, 6, 7, 8]). For bipartite graphs, a variety of cohesive subgraph models have been proposed to identify important structures, such as \((\alpha,\beta)\)-core [3], bitruss [9] and biclique [10]. Biclique is the most cohesive model, which requires the nodes inside to be fully connected. However, the computation complexity, i.e., NP-hard, makes it hard to apply in many time-efficient applications. Bitruss [11] adopts the butterfly motif (i.e., a \((2,2)\)-biclique) to investigate the cohesiveness of bipartite graphs. The \((\alpha,\beta)\)-core of bipartite graphs, which can be computed in linear time, has attracted great attention recently [3, 12, 13]. However, the model still has a drawback. Motivations: Given a bipartite graph \(G=(L,R,E)\), \((\alpha,\beta)\)-core is the maximal subgraph, where each node in \(L\) has at least \(\alpha\) neighbors in \(R\) while each node in \(R\) has at least \(\beta\) neighbors in \(L\). It can be computed in linear time by iteratively deleting the node with a degree less than \(\alpha\) or \(\beta\). For instance, in Figure 1, the subgraph consisting of nodes \(\{u_{2},u_{3},v_{2},v_{3},v_{4}\}\) is a (2,1)-core. However, in the \((\alpha,\beta)\)-core, it only emphasizes the engagement of each node, i.e., each node has a sufficient number of neighbors in the subgraph and treats each edge equally. However, in real applications, edges usually tend to have quite different weights. For example, in the customer-product network (e.g., Figure 1), each edge is assigned a weight, which reflects the frequency between a customer and a product. The frequency denotes the number of times the customer has bought the product. To make sense of the weight information, we propose a novel model, \((k,\omega)\)-core, to detect the densely frequent communities, which ensures that the nodes in the left layer have a sufficient number of neighbors and the nodes in the right layer have enough weights. Given a bipartite graph, the \((k,\omega)\)-core is the maximal subgraph where each node in \(L\) (resp. \(R\)) has at least \(k\) neighbors (resp. \(\omega\) weight). The weight of a node is the sum of the weights of each adjacent edge. For instance, reconsidering the graph in Figure 1, the weights of products \(\{v_{1},v_{2},v_{3},v_{4},v_{5}\}\) are \(\{1,5,5,3,1\}\), and the subgraph consisting of \(\{u_{1},u_{2},u_{3},v_{2},v_{3},v_{4}\}\) is a (2,2)-core. The nodes \(\{u_{4},v_{1},v_{5}\}\) are excluded from the (2,2)-core, since customer \(\{u_{4}\}\) has not bought a sufficient number of distinct products while products \(\{v_{1},v_{5}\}\) have not been purchased enough times. Applications: The proposed \((k,\omega)\)-core model can be used in many real-world applications, such as product recommendation and fraud detection. * Product recommendation: In a product-customer network (e.g., Figure 1), a \((k,\omega)\)-core means a group of users with sufficient common tastes. Then, we can use the group information for product recommendation. For example, in Figure 1, \(\{u_{1},u_{2},u_{3},v_{2},v_{3},v_{4}\}\) is the (2,2)-core. Then, we can recommend product \(v_{2}\) to user \(u_{3}\), since \(u_{3}\) shares many common interests with \(u_{1}\) and \(u_{2}\).