HCNTF: a high-order connectivity patterns-integrated non-negative tensor factorization approach for community discovery

Community discovery has become a key issue in complex network-related big data analysis. With good interpretability, latent factorization (LF) methods like non-negative matrix factorization (NMF) have been frequently utilized to develop community discovery models. However, most LF-based methods only focus on the lower-order topological information represented by the adjacency matrix of a network, ignoring the key role of the high-order connectivity patterns, e.g., high-order proximity and motif structure in the network, thus suffering from the loss of community discovery accuracy due to the incomplete structure information. Recently, some studies on high-order network structures-incorporated community discovery have been emerged, while they mainly focus on one type of high-order connectivity patterns. Moreover, existing methods that rely on motif networks constructed by specific high-order building blocks such as triangular structures disrupt foundational low-order topological arrangements, thereby introducing fragmentation effects that compromise the integrity of community detection outcomes. To overcome these issues, this paper proposes a High-order Connectivity patterns-integrated Non-negative Tensor Factorization (HCNTF) model for community discovery. It has four-fold ideas: a) incorporating high-order proximities into the original network via a well-designed network enhancement scheme to strengthen its structural information; b) constructing a high-order network based on motifs to represent the features of building blocks; c) leveraging a tensor to combine two kinds of high-order connectivity information with the original topology, and comprehensively extract the high- and low-order structure characteristics; and d) building a community discovery model with a Laplacian-regularized non-negative tensor factorization approach. Empirical studies on six real networks demonstrate the effectiveness of the proposed HCNTF model.