Statistical and Machine Learning Approaches for Network Analysis

10.5 Discussion

This chapter presented a general framework for the systematic extraction of dense patterns from simple or higher-order edge-weighted network data. It extends conventional relational set mining approaches [72,74,75] and clique-related network analysis [13,17,15]. The proposed reverse search algorithm allows for an effective, antimonotonicity-based pruning of the search space without missing any solutions; the complexity of the delay between two consecutive solutions is in the order of the input size. This property allows to apply it in cases where straightforward set enumeration algorithms are infeasible [4]. However, for large datasets or low density thresholds, the number of solutions can be prohibitive, making the computation slow in spite of the favorable runtime per solution.

There are several remedies for this problem. The first possibility is to maintain the enumerative search, but add further constraints based on additional criteria, prior knowledge, or external data [1], as described in Section 10.3.9. If relevant subsets are prespecified for some dimensions (for instance, windows of consecutive time intervals), reverse search with respect to the other dimensions can be performed for each of these subsets individually. On the other hand, one can use the reverse search strategy and additionally apply heuristic criteria or sampling techniques to control the number, overlap, and relevance of solutions; this allows to directly trade off the runtime and the completeness ...