# Cohesive Subgraph Identification in Weighted Bipartite Graphs
## 4 Index-Based Solution
### Time-Improved Method
In Algorithm 3, we first initialize the \(index\) and \(shrink\) as empty (Line 1). In Line 2, the algorithm computes \((0,\omega)\)-core as the initialization of the current processing row \(cRow\) and deals with each row in the main loop (Lines 4-17). We set the row next to the \(cRow\) as \(nRow\) at Line 4. Then, we compressed the storage space for all possible \((k,\omega)\)-cores in \(cRow\) (Lines 5-16). In each inner iteration, we first initialized both of the resulting sizes of the \((k,\omega)\)-cell after \(row\) shrink (\(rs\)) and \(column\) shrink (\(cs\)) as positive infinity. In Lines 7-8, we use RowIndex to shrink the \((k,\omega)\)-cell to the \((k,\omega+1)\)-cell and the resulting size of the \((k,\omega)\)-cell is reserved in \(rs\). Meanwhile, in Lines 9-10, we utilize ColumnIndex to shrink the \((k,\omega)\)-cell to the \((k+1,\omega)\)-cell and the resulting size of the \((k,\omega)\)-cell is reserved in \(cs\). It is obvious that smaller the resulting size of the \((k,\omega)\)-cell is, the better the result of compression. Hence, in Lines 11-16, for a specific \((k,\omega)\)-cell, if the value of \(rs\) is no larger than \(cs\), we choose RowIndex to compress and put the nodes contained in the \((k,\omega)\)-core but not in the \((k,\omega+1)\)-core into \((k,\omega)\)-cell, with the corresponding direction \"\(\rightarrow\)\" recorded in \(shrink\). Otherwise, we select ColumnIndex to compress, and put the nodes contained in the \((k,\omega)\)-core but not in the \((k+1,\omega)\)-core into \((k,\omega)\)-cell, with the corresponding direction \"\(\downarrow\)\" reserved in \(shrink\). We deal with each cell the same way one by one. Finally, we shrink the last \(row\) of the \(index\) in Line 18 by using Algorithm 2 and then return the resulting OptionIndex with its corresponding direction table \(shrink\) in Line 19. OptionIndex Query Algorithm: Based on the pre-computed OptionIndex, we devised an efficient option query algorithm, and the details are shown in Algorithm 4. In Line 1, we first initialize the \((k,\omega)\)-core \(Q\) as empty. In Lines 2-3, for given \(k\) and \(\omega\), we locate index\([k][\omega]\) and then add the nodes contained in the \((k,\omega)\)-cell to \(Q\). At the same time, we obtain the shrink direction \(d\) from \(shrink[k][\omega]\) (Line 4). In Lines 6-9, if the direction is \"\(\rightarrow\)\", it implies the current \((k,\omega)\)-cell adopts the \(row\) compression. Then, we add the nodes contained in the \((k,\omega+1)\)-cell to \(Q\) and then turn to the \((k,\omega+1)\)-cell. In Lines 10-13, if the direction is \"\(\downarrow\)\", it suggests that the shrink direction is down the column. Accordingly, the nodes stored in the \((k,\omega)\)-cell are added into \(Q\), and then we turn to \((k+1,\omega)\)-cell for the next iteration. The procedure terminates until the shrink direction is null and finally we return \(Q\) as the resulting \((k,\omega)\)-core. ```
Input : Bipartite graph: \(G=(L,R,E,W)\), degree constraint: \(k\), weight constraint: \(\omega\) Output : The \((k,\omega)\)-core of \(G\)
1\(Q\leftarrow\emptyset\);
2 Locate index[\(k\)][\(\omega\)];
3\(Q\gets Q\cup index[k][\omega\)];
4\(d\leftarrow\textit{shrink}[k][\omega]\);
5 while\(d\) is not nulldo
6 if\(d\) = \"\(\rightarrow\)\" then
7\(\omega\leftarrow\omega+1\);
8\(Q\gets Q\cup index[k][\omega]\);
9\(d\leftarrow\textit{shrink}[k][\omega]\);
10
11 elseif\(d\) = \"\(\downarrow\)\" then
12\(k\gets k+1\);
13\(Q\gets Q\cup index[k][\omega]\);
14\(d\leftarrow\textit{shrink}[k][\omega]\);
15
16 return\(Q\)
```
**Algorithm 4**OptionIndex based Query Algorithm

#### 4.3.3 Unionindex

To further reduce index cost, we propose the UnionIndex. The main difference between UnionIndex and OptionIndex is that we compress certain cells both in _row_ and _column_ directions at the same time to narrow more space. For example, recall that in Table 1, the \((1,1)\)-cell can be shrunk to the \((1,2)\)-cell with compression size 7, or to the \((2,1)\)-cell with compression size 8.