Search

Graphs, also known as networks, are an expressive data representation used in many domains. Numerous algorithms have been designed to find interesting patterns in graphs. However, they have at least one of two major drawbacks. First, most algorithms focus on finding complex subgraphs but ignore relationships between attributes. But attributes play a major role in several real-life applications such as for profile completion in social networks. Second, the user must generally set multiple parameters that greatly influence results but are unintuitive to set. To provide a solution to these issues, this paper introduces a novel algorithm named CSPM (Compressing Star Pattern Miner) for discovering compressing patterns in an attributed graph. The algorithm is parameter-free and discovers star-shaped attribute patterns that reveal strong relationships between attribute values by utilizing the concept of conditional entropy and the minimum description length principle. Extensive experiments on real data show that CSPM is efficient and can find insightful patterns. In particular, it is observed that the discovered patterns can boost the accuracy of state-of-the-art graph attribute completion models on social network databy up to 15.39%. Moreover, it is found that CSPM can uncover many interesting patterns describing alarm correlations in data from a large-scale industrial telecommunication network. [ABSTRACT FROM AUTHOR]

Highlights: [•] We present the anti-modularity as a quality measure of the anti-community detecting. [•] A label propagation algorithm LPAD for anti-community detection is proposed. [•] The proposed algorithm LPAD does not require the predefined number of anti-communities. [•] The proposed algorithm LPAD has low time complexity of O(n 2). [•] LPAD can maximize the number of edges between clusters and minimize the number of clusters. [ABSTRACT FROM AUTHOR]