With the rapid growth of online social networks, strengthening their stability has emerged as a key research focus. This study aims to identify influential relationships that significantly impact community stability. In this paper, we introduce and explore the anchor trussness reinforcement problem to reinforce the overall user engagement of networks by anchoring some edges. Specifically, for a given graph$G$and a budget$b$, we aim to identify$b$edges whose anchoring maximizes the trussness gain, which is the cumulative increment of trussness across all edges in$G$. We establish the NP-hardness of the problem. To address this problem, we introduce a greedy framework that iteratively selects the current best edge. To scale for larger networks, we first propose an upward-route method to constrain potential trussness increment edges. Augmented with a support check strategy, this approach enables the efficient computation of the trussness gain for anchoring one edge. Then, we design a classification tree structure to minimize redundant computations in each iteration by organizing edges based on their trussness. We conduct extensive experiments on 8 real-world networks to validate the efficiency and effectiveness of the proposed model and methods.

Community detection is a fundamental problem and has been extensively studied. With the abundance of information in real-world networks, the discovery of communities in attribute graphs is increasingly valuable. However, numerous previous models in attribute graphs neglect the fairness concept, which plays an important role in ensuring that graph analysis is not biased toward specific groups. In this paper, we propose a novel model, named proportional fair clique (PFC). Specifically, given an attribute graph G = (V, E, A), an integer k and a threshold λ ∊ [0, 1/|A|], a subgraph S of G is a PFC if (i) S is a clique with size at least k and (ii) |Sai |/|S| ≥ λ for each attribute ai in G, where Sai is the node set in S associated with attribute ai. We show that the problem of enumerating all the maximal proportional fair cliques (MPFC) is NP-hard. A reasonable baseline algorithm is first presented by extending the BronKerbosch framework. To scale for large networks, we propose several optimization strategies to accelerate the computation. Finally, comprehensive experiments are conducted over 6 graphs to demonstrate the efficiency and effectiveness of the proposed techniques and model.

A$k$-plex is a subgraph in which each vertex can miss edges to at most$k$vertices, including itself.$k$-plex can find many real-world applications such as social network analysis and product recommendation. Previous studies about$k$-plex mainly focus on static graphs. However, in reality, relationships between two entities often occur at some specific timestamps, which can be modeled as temporal graphs. Directly extending the$k$-plex model may fail to find some critical groups in temporal graphs, which exhibit certain frequent occurring patterns. To fill the gap, in this paper, we develop a novel model, named$(k,l)$-plex, which is a vertex set that exists in no less than$l$timestamps, at each of which the subgraph induced is a$k$-plex. To identify practical results, we propose and investigate two important problems, i.e., large maximal$(k,l)$-plex (MalKLP) enumeration and maximum$(k,l)$-plex (MaxKLP) identification. For the MalKLP enumeration problem, a reasonable baseline method is first proposed by extending the Bron-Kerbosch (BK) framework. To overcome the limitations in baseline and scale for large graphs, optimized strategies are developed, including novel graph reduction approach and search branch pruning techniques. For the MaxKLP identification task, we first design a baseline method by extending the proposed enumeration framework. Additionally, to accelerate the search, a new search framework with efficient branch pruning rules and refined graph reduction method is developed. Finally, comprehensive experiments are conducted on 14 real-world datasets to validate the efficiency and effectiveness of the proposed techniques.

Maximal k-plex enumeration is an important problem in graph analysis and can find many real-world applications. A k-plex is a subgraph in which every vertex can miss edges to at most$k$vertices (including itself). Previous studies mainly focus on static graphs. However, in reality, relationships between two entities often occur at some specific timestamps, which can be modeled as temporal graphs. Directly extending the k-plex model may fail to find some critical groups in temporal graphs, which exhibit certain frequent occurring phenomenon. To fill the gap, in this paper, we propose a novel model called$(k,\ l)$-plex, which is a vertex set that exists in no less than$I$timestamps, at each of which the subgraph induced is a$k$-plex. To identify practical results, we introduce the concept of large maximal$(k,\ l)$-plex (MalKLP), i.e., maximal$(k,\ l)$-plex with size no less than a given threshold. In this paper, we conduct the first attempt to propose and investigate the MalKLP enumeration problem, which is proved to be NP-hard. A reasonable baseline method called KLPE-BK is developed by extending the Bron-Kerbosch framework. To overcome the three limitations in KLPE-BK and scale for larger graphs, novel optimized strategies are proposed, including graph reduction, search branch pruning and maximality checking approaches. Finally, we present our optimized algorithm KLPE+ by integrating the techniques proposed. Comprehensive experiments on 8 real-world datasets are conducted to validate the efficiency and scalability of the proposed techniques. Compared with the baseline method, KLPE + can achieve up to two orders of magnitude speedup. A case study is conducted to verify the effectiveness of our model.

Cohesive subgraph mining is a fundamental problem in bipartite graph analysis. In reality, relationships between two types of entities often occur at some specific timestamps, which can be modeled as a temporal bipartite graph. However, the temporal information is widely neglected by previous studies. Moreover, directly extending the existing models may fail to find some critical groups in temporal bipartite graphs, which appear in a unilateral (i.e., one-layer) form. To fill the gap, in this paper, we propose a novel model, called maximal λ -frequency group (MFG). Given a temporal bipartite graph 𝒢 = (U, V, ℰ ), a vertex set V S ⊆ V is an MFG if i ) there are no less than λ timestamps, at each of which V S can form a ( τ U , τ V )-biclique with some vertices in U at the corresponding snapshot, and ii ) it is maximal. To solve the problem, a filter-and-verification (FilterV) method is proposed based on the Bron-Kerbosch framework, incorporating novel filtering techniques to reduce the search space and array-based strategy to accelerate the frequency and maximality verification. Nevertheless, the cost of frequency verification in each valid candidate set computation and maximality check could limit the scalability of FilterV to larger graphs. Therefore, we further develop a novel verification-free (VFree) approach by leveraging the advanced dynamic counting structure proposed. Theoretically, we prove that VFree can reduce the cost of each valid candidate set computation in FilterV by a factor of O (| V |). Furthermore, VFree can avoid the explicit maximality verification because of the developed search paradigm. Finally, comprehensive experiments on 15 real-world graphs are conducted to demonstrate the efficiency and effectiveness of the proposed techniques and model.

Finding bicliques is a fundamental problem in bipartite graph analysis, and can find numerous applications. However, previous studies only focus on unsigned bipartite graphs. Signed information, such as friend and enemy, naturally exists in real-world networks. It is critical to leverage signed information to better characterize biclique. To fill this gap, we propose a novel biclique model, named balanced signed biclique, by leveraging the property of balance theory. Specifically, given a signed bipartite graph$G$and two positive integers$\tau _{U}, \tau _{V}$, a subgraph$S=(U_{S},V_{S},E_{S})$of$G$is a balanced signed biclique if$i)$$S$is a biclique without any unstable motif, i.e., unbalanced butterfly, and$ii)$$|U_{S}| \geq \tau _{U}$and$|V_{S}| \geq \tau _{V}$. In this paper, we propose and investigate two important problems, i.e., maximal balanced signed biclique enumeration and maximum balanced signed biclique identification. Due to the unique features of signed bipartite graphs, the previous works cannot be applied to our problems directly. For the enumeration task, to construct a reasonable baseline, we extend the existing biclique enumeration framework for unsigned bipartite graphs and integrate the developed balanced bipartite graph property. To scale for large networks, optimized strategies are proposed to overcome the three limitations in the baseline method. For the identification task, we first propose a baseline method by leveraging the proposed enumeration framework. Moreover, employing novel optimizations, an anchor balanced bipartite graph based search framework is introduced to accelerate the search. Finally, extensive experiments are conducted on 8 real-world datasets to demonstrate the efficiency and effectiveness of the proposed techniques and model.

Maximum biclique identification, which aims to find the biclique with the largest size, can find a wide spectrum of applications in different domains, such as E-Commerce, healthcare and bioinformatics. However, the previous studies mainly focus on unsigned bipartite graphs. The signed information naturally exists in real applications, such as like and dislike. The neglect of signed information may fail to discover the inherent properties of networks. In this paper, we propose a novel model, named signed (k,l)-biclique (SKLB), by enforcing constraints over the number of positive and negative connections. Specifically, given a signed bipartite graph and two positive integers k,l, SKLB is a biclique, where each vertex has no less than k positive neighbors and no more than l negative neighbors. We prove the problem of finding the maximum signed (k,l)-biclique (MaxSKLB) is NP-hard. Moreover, we show that the problem is still NP-hard, even if the input graph is a biclique itself. A baseline algorithm is first presented through biclique enumeration, which tries to find the MaxSKLB for each encountered biclique and return the largest one. However, considering that the extraction of MaxSKLB from a biclique is still NP-hard, a greedy strategy is developed to accelerate the processing with competitive result. Furthermore, to efficiently handle large graphs, we optimize the algorithm from different perspectives, including unnecessary search branches and unpromising vertices filtering. Finally, comprehensive experiments are conducted over 10 graphs to validate the efficiency and effectiveness of proposed techniques and model.

The maximum clique problem, which is to find the clique with the largest size, can find many real-world applications and is notable for its capability of modeling many combinatorial problems. However, most existing research focuses on processing unsigned graphs, i.e., treat each connection equally. In real applications, edges of graphs are usually associated with signed information, i.e., positive or negative edges, and signed graph analysis has attracted great attentions in the recent. In this paper, we first analyze the disadvantages of existing signed clique models, and then propose a novel clique model, named signed$\theta$-clique. Given a signed graph$G$and a subgraph$S$, let$d^{+}_{S}(u)$and$d^{-}_{S}(u)$be the number of positive and negative neighbors of vertex$u$in$S$. We say a subgraph$S$is a signed$\theta$-clique if$i)$$S$is a clique and$ii)$each vertex$u$in$S$fulfills$d^{+}_{S}(u) - d^{-}_{S}(u) \geq \theta$. We show that the problem of identifying the maximum signed$\theta$-clique is NP-hard. Novel pruning techniques are proposed to reduce the searching space. In addition, efficient searching strategies are developed to scale for large graphs. Comprehensive experiments on 8 real-world datasets are conducted to demonstrate the effectiveness and efficiency of the proposed approaches.

In social networks, dense relationships among users contribute to stable communities. Breakdowns of critical connections may cause users to leave the group. A popular model to measure the cohesiveness of a network is k-core or coreness. To identify important connections, in this paper, we propose and investigate the problem of k-core minimization problem under three different metrics. Specifically, given a graph G and a budget b, we aim to retrieve a set B of b edges for deletion purpose, which can minimize i) the number of nodes in the collapsed k-core (KNM), ii) the number of edges in the collapsed k-core (KEM), and iii) the overall coreness decreased in the target node set P (KCM). We first formally define the problems and prove that the three problems are all NP-hard. Then, a baseline greedy searching framework is developed. To scale for large graphs, optimized algorithms are developed by integrating novel pruning strategies and group-based structures. Finally, comprehensive experiments on 6 real social networks are conducted to demonstrate the efficiency and effectiveness of our proposed models and methods.

Clique, as a fundamental model for graph analysis, is widely investigated in the literature. However, with the emergence of various graph data, such as signed graph, novel clique model is desired to better capture the cohesiveness within these graphs. Different from unsigned graphs, where only one type of edge exists, in signed graphs, nodes can be connected either positively or negatively (e.g., friend or enemy). In this article, we propose a novel clique model, called signed$k$-clique, which aims to find cohesive subgraphs in signed networks based on the classic clique model and balance theory. Given a signed graph$G$, an induced subgraph$S$is a signed$k$-clique if$|S| \geq k$and$S$is a clique without any unbalanced triangle. Moreover, we propose and investigate two fundamental problems, i.e., maximal signed$k$-clique enumeration and maximum signed$k$-clique identification, both of which are shown to be NP-hard. For maximal signed$k$-clique enumeration, novel balance graph based search framework and optimization techniques are proposed to eliminate the limitations in the developed baseline. For maximum signed$k$-clique identification, different upper bound based techniques are developed to early terminate the search. Furthermore, the support of finding top-$\gamma$results is also discussed. Finally, comprehensive experiments on seven real-world datasets are conducted to demonstrate the efficiency and effectiveness of the proposed techniques. Compared with the baseline, the optimized algorithm can achieve up to four orders of magnitude speedup.

The reachability query is a fundamental problem in graph analysis. Recently, many studies focus on label-constraint reachability queries, which tries to verify whether two vertices are reachable under a given label set. However, in many real-life applications, it is more practical to find the minimum label set required to ensure the reachability of two vertices, which is neglected by previous research. To fill the gap, in this paper, we propose and investigate the minimum reachable label set (MRLS) problem in edge-labeled graphs. Specifically, given an edge-labeled graph and two vertices s, t, the MRLS problem aims to find a label set L with the minimum size such that s can reach t through L. We prove the hardness of our problem, and develop different optimization strategies to improve the scalability of the algorithms. Extensive experiments on 6 datasets demonstrate the advantages of the proposed algorithms.

Maximum clique identification is a fundamental problem for many domains. In real-world applications, signed information, e.g., friend and enemy, naturally exists in graphs. However, most existing research focuses on unsigned graph analysis. In this paper, we propose a new clique model for signed graphs, named signed$\theta$-clique. We show that the problem of identifying the maximum signed$\theta$-clique is NP-hard. To scale for large signed graphs, novel pruning rules and search strategies are developed. Extensive experiments are conducted on 8 real-world graphs to verify the advantages of proposed model and techniques.

Community detection is a fundamental problem in graph analysis, while most existing research focuses on unsigned graphs. In many applications, networks involve both positive and negative connections. It is important to exploit the signed information to identify more stable communities. In this paper, we propose a novel model, named stable k-core, to measure the stability of a community in signed graphs by leveraging the concept of balance theory. We show that the problem of finding the maximum stable k-core is NP-hard. Advanced approaches are proposed to accelerate the processing. Experiments on 6 signed networks are conducted to verify the efficiency and effectiveness of proposed model and techniques.

Maximal biclique enumeration is a fundamental problem in bipartite graph analysis, and can find numerous applications. However, previous studies only focus on unsigned bipartite graphs. Signed information, such as friend and enemy, naturally exists in real-world networks. It is critical to leverage signed information to better characterize biclique. To fill this gap, in this paper, we propose a novel biclique model, named balanced signed biclique, by leveraging the property of balance theory. Specifically, given a signed bipartite graph$G$, two positive integers$\tau_{U}, \tau_{V}$, a subgraph$S=(U_{S},\ V_{S},\ E_{S})$of$G$is a balanced signed biclique if$i$)$S$is a biclique without any unstable motif, i.e., unbalanced butterfly, and ii)$\vert U_{S}\vert \geq\tau_{U}$and$\vert V_{S}\vert \geq\tau_{V}$. In this paper, we aim to enumerate all the maximal balanced signed bicliques, which is proved to be NP-hard. Moreover, due to the unique features of signed bipartite graphs, the previous works cannot be applied to our problem directly. To construct a reasonable baseline, we extend the existing biclique enumeration framework for unsigned bipartite graphs and integrate the developed balanced bipartite graph property. To scale for larger networks, novel optimized strategies are proposed to overcome the three limitations in the baseline method. Extensive experi-ments are conducted on 8 real-world datasets to demonstrate the efficiency and effectiveness of proposed techniques and model. Compared with the baseline approach, the optimized algorithm can achieve up to 3 orders of magnitude speedup.

Community detection is one of the most fundamental problems in social network analysis, while most existing research focuses on unsigned graphs. In real applications, social networks involve not only positive relationships but also negative ones. It is important to exploit the signed information to identify more stable communities. In this paper, we propose a novel model, named stable$k$-core, to measure the stability of a community in signed graphs. The stable$k$-core model not only emphasizes user engagement, but also eliminates unstable structures. We show that the problem of finding the maximum stable$k$-core is NP-hard. To scale for large graphs, novel pruning strategies and searching methods are proposed. We conduct extensive experiments on 6 real-world signed networks to verify the efficiency and effectiveness of proposed model and techniques.

Abstract Community search, which aims to retrieve important communities (i.e., subgraphs) for a given query vertex, has been widely studied in the literature. In the recent, plenty of research is conducted to detect influential communities, where each vertex in the network is associated with an influence value. Nevertheless, there is a paucity of work that can support personalized requirement. In this paper, we propose a new problem, i.e., maximal personalized influential community search. Given a graph G, an integer k and a query vertex u, we aim to obtain the most influential community for u by leveraging the k-core concept. To handle larger networks efficiently, two algorithms, i.e., top-down algorithm and bottom-up algorithm, are developed. In real-life applications, there may be a lot of queries issued. Therefore, an optimal index-based approach is proposed in order to meet the online requirement. In many scenarios, users may want to find multiple communities for a given query. Thus, we further extend the proposed techniques for the top-r case, i.e., retrieving r communities with the largest influence value for a given query. Finally, we conduct extensive experiments on 6 real-world networks to demonstrate the advantage of proposed techniques.

Mining cohesive subgraphs is a fundamental problem in social network analysis. The k-truss model has been widely used to measure the cohesiveness of subgraphs. Most existing studies about k-truss focus on unsigned graphs. However, in real applications, the edges in the networks can be either positive or negative, e.g., friend or foe relationships, which represents more information than unsigned networks. Therefore, the traditional k-truss model is not applicable for the signed networks. Motivated by this, in this paper, we propose a novel model, named signed (k,r)-truss, which leverages the property of balanced triangle in singed network analysis. Specifically, a signed (k,r)-truss is a subgraph where each edge has no less than k balanced support and no more than r unbalanced support. We prove that the problem of identifying the maximum signed (k,r)-truss is NP-hard. Due to the hardness of the problem, we tend to the heuristic strategies. A trivial algorithm is first presented. Then, two greedy algorithms are developed to enhance the processing. Finally, we conduct comprehensive experiments on real-world signed networks to verify the performance of proposed techniques.

Community detection is a fundamental problem in social network analysis, and most existing studies focus on unsigned graphs, i.e., treating all relationships as positive. However, friend and foe relationships naturally exist in many real-world applications. Ignoring the signed information may lead to unstable communities. To better describe the communities, we propose a novel model, named signed k-truss, which leverages the properties of k-truss and balanced triangle. We prove that the problem of identifying the maximum signed k-truss is NP-hard. To deal with large graphs, novel pruning strategies and algorithms are developed. Finally, we conduct comprehensive experiments on real-world signed networks to evaluate the performance of proposed techniques.

Community search is a fundamental problem in social network analysis. In this paper, we propose a novel problem, called influential maximum connected community (IMCC) search, which leverages the k-ECC model to measure the cohesiveness of subgraphs and tries to find the influential community for a set of query vertices.