# Cohesive Subgraph Identification in Weighted Bipartite Graphs
## 4 Index-Based Solution
### Time-Improved Method  
The baseline index method is time-consuming, since we need to compute all the possible \((k,\omega)\)-cores one by one. Due to the nested property of \((k,\omega)\)-core, many subgraphs will be computed multiple times. To reduce the time consumption, we resort to the time-improved solution by escaping the unnecessary \((k,\omega)\)-core computations. Before \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \(k\)/\(\omega\) & \(\mathbf{1}\) & \(\mathbf{2}\) & \(\mathbf{3}\) & \(\mathbf{4}\) & \(\mathbf{5}\) \\ \hline \multirow{2}{*}{\(1\)} & \(u_{1},u_{2},u_{3},u_{4}\) & \(u_{1},u_{2},u_{3},u_{4}\) & \(u_{1},u_{2},u_{3},u_{4}\) & \(u_{1},u_{2},u_{3}\) & \(u_{1},u_{2},u_{3}\) \\  & \(v_{1},v_{2},v_{3},v_{4},v_{5}\) & \(v_{2},v_{3},v_{4}\) & \(v_{2},v_{3},v_{4}\) & \(v_{2},v_{3},v_{4}\) & \(v_{2},v_{3}\) & \(v_{2},v_{3}\) \\ \hline \multirow{2}{*}{\(2\)} & \(u_{1},u_{2},u_{3}\) & \(u_{1},u_{2},u_{3}\) & \(u_{1},u_{2}\) & \(u_{1},u_{2}\) & \multirow{2}{*}{\(u_{1},u_{2}\)} \\  & \(v_{1},v_{2},v_{3},v_{4},v_{5}\) & \(v_{2},v_{3},v_{4}\) & \(v_{2},v_{3}\) & \(v_{2},v_{3}\) & \\ \hline \multirow{2}{*}{\(3\)} & \(u_{1},u_{3}\) & \multirow{2}{*}{\(v_{1},v_{2},v_{3},v_{4},v_{5}\)} & & & \\  & & & & & & \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Index construction example. Figure 2: General framework of the online and index-based solutions. going to the detailed method, we first introduce the concept of \(\omega_{max,k}(u)\) to help present the algorithm. Definition 2 (\(\omega_{max,k}(u)\)): Given a weighted bipartite graph \(G=(U,E,W)\), where \(U=R\cup L\), and a specific value \(k\), for each node \(u\in U\), \(\omega_{max,k}(u)\) is the maximum value of \(\omega\) for which there exists a \((k,\omega)\)-core that contains \(u\). For a node \(u\in U\) and a specific value \(k\), we know that the \((k,\omega_{max,k}(u))\)-core contains \(u\) by Definition 2. According to the nested property of \((k,\omega)\)-core by Lemma 1, we can infer that the \((k,\omega_{max,k}(u))\)-core is also contained in \((k,\omega_{i})\)-cores of \(G\), where \(\omega_{i}\) is no larger than \(\omega_{max,k}(u)\). Thus, there are many redundant computations in the process of constructing index structure. To address the above concerns, we devise an improved index-based algorithm. Given a graph \(G\) and an integer \(k\), we first compute \(\omega_{max,k}(u)\) for each node \(u\in U\) and then store \(u\) in the \((k,\omega)\)-cells where \(0\leq\omega\leq\omega_{max,k}(u)\). Note that we store all nodes in _row_ for a specific input \(k\). The details are shown in Algorithm 2. ```
Input : Bipartite graph: \(G=(L,R,E,W)\) Output : Constructed index
1 Initialize _row_ { } \(\leftarrow\)\(\emptyset\), \(\omega\)\(\leftarrow\) 1;
2\(G^{\prime}=(L^{\prime},R^{\prime},E^{\prime},W^{\prime})\)\(\leftarrow\)Generate \((k,0)\)-core;
3 while\(G^{\prime}\) is not emptydo
4 while\(\exists u\in L^{\prime}:d(u)<k\vee\exists v\in R^{\prime}:w_{t}(v)<\omega\)do
5 forach\(u\in L^{\prime}\wedge d(u)<k\)do
6 foreach\(v\in N(u)\)do
7\(w_{t}(v)\gets w_{t}(v)-w(u,v)\);
8\(L^{\prime}.remove(u)\);
9 for\(i=0\) to \(\omega-1\)do
10 Put \(u\) into _row_[\(i\)];
11
12
13 forach\(v\in R^{\prime}\wedge w_{t}(v)<\omega\)do
14 forach\(u\in N(v)\)do
15\(d(u)\gets d(u)-1\);
16\(R^{\prime}.remove(v)\);
17 for\(i=0\) to \(\omega-1\)do
18 Put \(v\) into _row_[\(i\)];
19
20
21
22
23
24
25
26
27
28
29
30
310
32
334
35
36
37
38
390
391
392
401
42
433
445
456
467
47
582
593
694
695
796
897
989
998
1000
111
112
113
114
115
116
117
118
1190
1201
121
1223
1242
125
126
127
128
1290
2910
3131
3201
3212
322
3333
345
3696
370
3971
382
398
3999

40



be stored in multiple cells due to the nested property. For instance, given a fixed \(k=1\), the nodes in the \((1,3)\)-cell will also be stored in \((1,1)\)-cell, \((1,2)\)-cell and \((1,3)\)-cell. Similarly, for a specific \(\omega\), the same problem still exists when computing the column index. ### Advanced Index Structures

As discussed, the baseline index method suffers from storage issues.