Mining Maximal Clique Summary with Effective Sampling Maximal clique enumeration (MCE) is a fundamental problem in graph theory and is used in many applications, such as social network analysis, bioinformatics, intelligent agent systems, cyber security. Most existing MCE algorithms focus on improving the efficiency rather than reducing the size of the output, which could consist of a large number of maximal cliques. In this paper, we study how to report a summary of less overlapping maximal cliques. The problem was studied before, however, after examining the pioneer approach, we consider it still not satisfactory. To advance the research along this line, this paper attempts to make two contributions: (a) We propose a more effective sampling strategy, which produces a much smaller summary but still ensures that the summary can somehow witness all the maximal cliques and the expectation of each maximal clique witnessed by the summary is above a predefined threshold. (b) To verify experimentally, we tested ten real benchmark datasets that have a variety of graph characteristics. The results show that our new sampling strategy consistently outperforms the stateoftheart method by producing smaller summaries and running faster on all the datasets.

Sampling informative patterns from large single networks Abstract   The set of all frequent patterns that are extracted from a single network can be huge. A technique recently proposed for obtaining a compact, informative and useful set of patterns is output sampling, where a small set of frequent patterns is randomly chosen. However, existing output sampling algorithms work only in the transactional setting, where the database consists of a collection of relatively small graphs. In this paper, first we extend the output sampling framework to the single network setting where the database is a large single graph, counting supports of patterns is more complicated, and frequent patterns might be sampled based on any arbitrary target distribution. Then, we propose sampling techniques that are based on more interestinginformative measures or those that are specific to large single networks, such as product of the pattern size with its support, network compressibility, and pattern density. Finally, we study the empirical behavior of our algorithm in a realworld case study.