# Cohesive Subgraph Identification in Weighted Bipartite Graphs
## 4 Index-Based Solution
### Performance Evaluation  
To evaluate the efficiency, we compare the response time and space storage of the algorithms on the datasets as follows. Efficiency of the time-improved algorithm: We firstly compared the baseline solution (BL) with the time-improved algorithm (TI) over all the datasets for index construction. The results are shown in Figure 3. It is obvious that TI runs much faster than BL, since BL needs to compute each subgraph from scratch. In particular, TI significantly outperforms BL in large graphs. For instance, in the Books dataset, TI can achieve a speed that is up to 42X faster. Evaluation of index-construction time: To evaluate the performance of different strategies, in Figure 4, we report the index construction time of TI, TI+Row, TI+Option and TI+Union. We vary the percentage of nodes selected as the input graph. As expected, more nodes will lead to a higher index construction time. TI+Union is slower than the other methods, since it is the most complex method for index construction. The rank of the time costs for the three index construction methods is: RowIndex < OptionIndex < UnionIndex. Note that the highest time cost gap is in the order of seconds, which is tolerable for many applications. \begin{table}
\begin{tabular}{l l l l} \hline \hline
**Dataset** & **L Layer** & **R Layer** & **Edges** \\ \hline Pedia & 6325 & 24,952 & 25,039 \\ Movielens & 7588 & 16,528 & 63,135 \\ News & 1408 & 25,138 & 105,039 \\ Quote & 21,607 & 94,756 & 232,924 \\ Books & 32,583 & 134,942 & 432,092 \\ Citeulike & 22,715 & 791,763 & 1,531,769 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Statistics of datasets. Figure 3: Efficiency evaluation of the time-improved algorithm. Evaluation of the index space: In this experiment, the space costs are compared among the four index-construction algorithms, i.e., TI, TI+Row, TI+Option and TI+Union. Note that the space storage is measured by the number of nodes stored inside the index. Similarly, we vary the percentage of nodes in each dataset. The results are shown in Figure 5. As observed, with the increase in nodes involved, more index space is required for all the algorithms. Obviously, the space cost of TI+Union is much less than that of TI, which can save up to 7X space in the News dataset. As expected, TI+Union greatly outperforms TI+Row and TI+Option, for it can omit the largest number of unpromising copies of nodes. The rank of the space cost for these methods is: UnionIndex < OptionIndex < RowIndex. Effect of \(k\) in \((k,\omega)\)-core queries: To evaluate the querying performance of proposed techniques, we report the response time of GCore, TI+Row, TI+Option and TI+Union algorithms on the three largest datasets by varying \(k\). The results are shown in Figure 6. As shown, with the increase in \(k\), the response time of each algorithm decreases. This is because the returned densely frequent community size become smaller when the degree constraint \(k\) becomes tighter. Moreover, there is no doubt that all the index-based query algorithms run much faster than GCore for all \(k\) values. The main reason is that the index-based algorithms pre-compute the \((k,\omega)\)-core information, so that we can quickly obtain the related nodes when querying any \((k,\omega)\)-core. Figure 4: Evaluation of index-construction time. Figure 5: Evaluation of the index space. Effect of \(\omega\) in \((k,\omega)\)-core queries: In Figure 7, we report the response time of GCore, TI+Row, TI+Option and TI+Union by varying \(\omega\). With the increase in \(\omega\), the response time decreases for all the algorithms, since the size of the detected cohesive subgraph decreases accordingly. The index-based solutions are much faster than the online solution, i.e., GCore. As shown, more complex index structures, such as TI+Union, will lead to a higher computation cost. Therefore, users can make a trade-off between the querying time and space cost when selecting the index strategies.