# Cohesive Subgraph Identification in Weighted Bipartite Graphs
## 2 Preliminaries  
We use \(G=(L,R,E,W)\) to denote a weighted bipartite graph, where nodes in \(G\) are partitioned into two disjoint sets \(L\) and \(R\), such that each edge from \(E\subseteq L\times R\) connects two nodes from \(L\) and \(R\), respectively. We use \(n=|L|+|R|\) and \(m=|E|\) to denote the number of nodes and edges, respectively. \(N(u)\) is the set of adjacent nodes of \(u\) in \(G\), which is also called the neighbor set of \(u\) in \(G\). The degree of a node \(u\in L\), denoted by \(d(u)\), is the number of neighbors of \(u\) in \(G\). For each edge \(e(u,v)\), we assign it a positive weight \(w(u,v)\in W\), defined as the frequency of edge \(e(u,v)\). The weight of a node \(v\in R\), denoted by \(w_{t}(v)=\sum_{u\in N(v)}w(u,v)\), is the sum of weights of each adjacent edge. We use \(k_{max}=max\{d(u)|u\in L\}\) and \(\omega_{max}=max\{\omega(v)|v\in R\}\) to denote the maximum degree and weight for nodes in \(G\), respectively. For a bipartite graph \(G\) and two node sets \(L^{\prime}\subseteq L\) and \(R^{\prime}\subseteq R\), the bipartite subgraph induced by \(L^{\prime}\) and \(R^{\prime}\) is the subgraph \(G^{\prime}\) of \(G\) such that \(E^{\prime}=E\cap(L^{\prime}\times R^{\prime})\). To evaluate the cohesiveness and frequency of communities in weighted bipartite subgraphs, we resort to the minimum degree for node set \(L\) and minimum weight for node set \(R\). In detail, for an induced subgraph, we request that nodes in \(L^{\prime}\) have a degree of at least \(k\) and nodes in \(R^{\prime}\) have a weight no less than \(\omega\).  
**Definition 1** (\((k,\omega)\)-core).: _Given a weighted bipartite graph \(G=(L,R,E,W)\) and two query parameters \(k\) and \(\omega\), the induced subgraph \(S=(L^{\prime},R^{\prime},E^{\prime},W^{\prime})\) is the \((k,\omega)\)-core of \(G\), denoted by \(C_{k,\omega}\), if \(S\) satisfies:_  
* _Degree constraint. For each node_ \(u\in L^{\prime}\)_, it has degree at least_ \(k\)_, i.e.,_ \(d(u,S)\geq k\)_;_
* _Weight constraint. For each node_ \(v\in R^{\prime}\)_, it has weight no less than_ \(\omega\)_, i.e.,_ \(\omega_{1}(v,S)\geq\omega\)_;_
* _Maximal. Any supergraph_ \(S^{\prime}\supset S\) _is not a_ \((k,\omega)\)_-core._  
**Example 1**.: _Figure 1 is a toy weighted bipartite graph for modeling the customer-product affiliations. It consists of two layers of nodes, i.e., the four nodes in the left layer denote the customers and five nodes in the right layer denote the products. The edges between nodes represent the purchase relationships and the weight of edges reflects the purchase frequency. Given the query parameters \(k=2\) and \(\omega=4\), we can obtain \(C_{2,4}\) consisting of nodes \(\{u_{1},u_{2},v_{2},v_{3}\}\)._  
For simplicity, we refer to a weighted bipartite graph as a graph, and omit \(G,S\) in the notations if the context is self-evident. In the following lemma, we show that \((k,\omega)\)-core has the nested property. It is easy to verify the correctness of the lemma based on the definition. Thus, we omit the proof here.  
**Lemma 1**.: _Given a weighted bipartite graph \(G\), the \((k^{\prime},\omega^{\prime})\)-core is nested to the \((k,\omega)\)-core, i.e., \(C_{k^{\prime},\omega^{\prime}}\subseteq C_{k,\omega}\), if \(k^{\prime}\geq k\) and \(\omega^{\prime}\geq\omega\)._  
**Example 2**.: _As shown in Example 1, \(C_{2,4}\) consists of nodes \(\{u_{1},u_{2},v_{2},v_{3}\}\). Suppose \(k=2\) and \(\omega=2\). We can find that \(C_{2,2}\) contains \(C_{2,4}\), i.e., \(C_{2,2}=\{u_{1},u_{2},u_{3},v_{2},v_{3},v_{4}\}\supseteq C_{2,4}\)._  
**Problem 1**.: _Given a weighted. bipartite graph \(G\) and two query parameters \(k\) and \(\omega\), we aim to design algorithms to compute the \((k,\omega)\)-core correctly and efficiently._