An Exact Algorithm for Maximum k-Plexes in Massive Graphs

1 Introduction

With rapid growth of the information technology, real-world graphs have been growing quickly in the past decade. A significant challenge rises: traditional algorithms fail to deal with newly emerged massive graphs. Therefore, algorithms in massive graphs (or complex networks) have received much attention due to their great importance in real-world applications. There has been a huge amount of efforts devoted to solve various problems, such as maximum cliques [Batsyn et al., 2014; Cai and Lin, 2016], and graph coloring [Rossi and Ahmed, 2014]. Among those problems, the maximum clique can settle various applications [Lakhlef, 2015; Conte et al., 2016].

Due to the strict restrictions of cliques, it is always difficult to model problems directly, so the k-plex was proposed and investigated [Seidman and Foster, 1978; Balasundaram et al., 2011; Conte et al., 2017]. Unlike cliques that restrict a vertex should connect with all other vertices, the k-plex allows every vertex has several missing connections, and thus it is more useful than the clique. Recently, the k-plex has revealed great success in the social network detection [Xiao et al., 2017; Miao and Balasundaram, 2017]. To solve the maximum k-plex, several algorithms were developed, including exact algorithms [Balasundaram et al., 2011; Moser et al., 2012] as well as heuristic methods [Zhou and Hao, 2017]. Moreover, enumeration algorithms for finding all maximal k-plexes larger than a predefined integer were also developed [Berlowitz et al., 2015; Conte et al., 2017]. In recent years, massive graphs have attracted much attention. There are many maximum clique algorithms aiming at massive graphs [Jiang et al., 2017; Cai and Lin, 2016; Rossi et al., 2014]. For example, Jiang et al. [2017] proposed an exact algorithm able to deal with very large garphs. But we have reviewed much fewer algorithms for the maximum k-plex. This is partially because the k-plex is more difficult to solve than cliques due to the relaxation. Among maximum k-plex algorithms, we highlight an exact algorithm proposed by Xiao et al. [2017] very recently, which breaks the trivial exponential bound of 2n for k ≥ 3 and solves graphs containing 10 thousand vertices.

∗ corresponding author

However, real-world graphs have grown extremely large in recent applications. The graphs may include millions of vertices and millions of edges. Those graphs are usually sparse and the degrees follow a power-law distribution. In this paper, we propose an exact algorithm to solve the maximum k-plex problem in massive sparse graphs. The algorithm is based on the framework of the branch-and-bound search and integrated with graph reduction methods and heuristic strategies. First, three reduction methods based on the lower bound are introduced, two of which are particularly developed for sparse graphs through a deep analysis of the structure of induced subgraphs. Moreover, a reduction method using the parameter k is also discussed as a further enhancement. Combinations of these methods are employed in two types of branches, i.e., selecting or discarding a vertex, to reduce search space. Also, reduction methods are performed in the preprocessing so as to simplify initial graphs. In addition, we employ heuristic methods to implement the dynamic vertex selection with the purpose of making the remaining graph as small as possible. Intensive experiments are performed on real-world graphs from Network Data Repository online [Rossi and Ahmed, 2015] and DIMACS benchmarks. First, it shows graphs can be reduced greatly through our preprocessing method. Also, comparative results are analyzed with varying k from 2 to 5, showing that our new algorithm solves graphs up to millions of vertices efficiently and outperforms the existing exact algorithms proposed recently. Finally, we give some conclusions.

2 Preliminaries

Graphs discussed in this paper are simple and undirected. Formally, an undirected graph is defined as G = (V,E), where V is a set of vertices and E is a set of edges. An edge in E is associated with two vertices in V , so an unordered pair of two vertices specifies an edge. We say a vertex u is a neighbor of a vertex v if there is an edge (v, u) in E. The set of the neighbors of a vertex v in V is denoted by NG(v). Specially, we define NG(v) as an empty set if v is not in V . The degree of a vertex v is defined as the number of its neighbors, denoted as dG(v) = |NG(v)|. Given a subset S ⊆ V , G[S] = (V ′ , E′ ) is the induced subgraph in G by S if V ′ = S and the edge set E′ consists of all the edges in E whose both vertices are in S.

Given a graph G = (V, E) and a positive integer k, a subset S ⊆ V is a k-plex if the degree of each vertex in the induced subgraph G[S] is at least |S|-k. We say a k-plex is maximal if any other k-plex cannot strictly contain it. The maximum k-plex problem is to find the k-plex with the largest size of a given graph. It is easy to see a 1-plex is a clique. It is proved that finding a k-plex with a fixed size is NP-complete for any constant positive integer k [Balasundaram et al., 2011].

3 Graph Reductions

In this section, we present some new theoretical results useful for graph reductions.

3.1 Properties

The first result is straightforward.

Property 1. Given a graph G = (V, E), and a positive integer LB, a vertex v cannot be included in a k-plex larger than LB if dG(v) + k ≤ LB.

Obviously, Property 1 is correct due to the definition of the k-plex. Such vertex v can be removed from the graph when we search a k-plex larger than LB. However, the effect of this property is limited since it basically relies on vertex degrees.

To reduce more vertices, a complex situation is discussed below. We provide some notions first. Given a graph G = (V,E), a k-plex S ⊆ V , and a vertex u in V , we define the notation rG,S(u) as

It indicates that a maximal k-plex containing S ∪ {u} can further include at most rG,S(u) vertices from V \ (S ∪ {u} ∪ NG(u)). Note that u can be either an element in S or in V \S. The notation cG,S(u, v) is defined as

cG,S(u, v) = min(dG′ (u)+rG,S(u)+1, |V ′ |)+rG,S(v), (2) where G′ (V ′ , E′ ) = G[(NG(v)\S)∪{v}], v is a vertex in V , u is a vertex in V ′ \ {v}, and function min returns the smaller value between two parameters.

Property 2. Given a graph G = (V, E) and a k-plex S ⊆ V , the maximum k-plex including S ∪ {u, v} is no larger than cG,S(u, v) + |S \ {v}|, where v is a vertex in V and u is a vertex in NG(v) \ S.

Proof. Let G′ (V ′ , E′ ) = G[(NG(v) \ S) ∪ {v}]. We divide vertices from V \ S into 2 parts: the first one is V \ (V ′ ∪S), from which we can choose rG,S(v) vertices at most due to the restriction on non-neighbors of v; the second one is V ′ . After u and v are selected, due to the restriction on non-neighbors of u, at most dG′(u) - |{v}| + rG,S(u) extra vertices can be selected in V ′ if there are enough vertices. Otherwise, all vertices in |V ′ | can be selected legally. So min(dG′(u) + rG,S(u)+1, |V ′ |) is an upper bound of the vertices including u and v from V ′ , and thus the the maximum k-plex including S ∪ {u, v} is no larger than cG,S(u, v) + |S \ {v}|.

Property 3. Given a graph G = (V, E), a k-plex S ⊆ V , a vertex v in S, and a vertex u in NG(v) \ S, S ∪ {u} cannot be involved in a k-plex larger than a positive integer LB if cG,S(u, v) + |S| - 1 ≤ LB.

It is easy to see Property 3 is correct according to Property 2. Furthermore, we can also apply Property 2 to make a further reduction. When we try to add a vertex v into S, we can check each vertex u in G′ = G[(NG(v) \ S) ∪ {v}], and remove the vertex u (u ̸= v) satisfying Property 2 under a given lower bound LB temporarily. We use V ∗ to denote the remaining vertex set of G′ . After that, we can count the vertices in V ∗ to determine whether v can be removed or added into S. Thereafter, we have the following property.

Property 4. Given a graph G=(V, E), a k-plex S ⊆ V and a vertex v in V \ S, S ∪ {v} cannot be included in a k-plex larger than a positive integer LB if there exists a remaining vertex set V ∗ such that |S| + |V ∗ | + rG,S(v) ≤ LB.

Proof. It is obvious that we can choose at most rG,S(v) vertices from V \ (S ∪ V ∗ ). With the case that all vertices in V ∗ can be selected, we obtain |S| + |V ∗ | + rG,S(v) as an upper bound of the k-plex. Thereafter, v cannot be included in a k-plex larger than LB.

To explain Property 4, we provide an example shown in Figure 1, where S = {s1}. Then we check v, and have G′ = G[(NG(v) \ S) ∪ {v}] composed of u, v and w3. In the case k = 2 and LB = 4, we have rG,S(v) = 1, rG,S(u) = 0 and dG′(u) = 1, and thus cG,S(u, v) + |S| = 4 equal to LB. Therefore, u is removed from G′ temporarily, and thus V ∗ = {v, w3}. Then, we have |S| + |V ∗ | + rG,S(v) = 4, so v should be removed when searching a k-plex larger than 4.

Property 4 is useful for further reduction on remaining vertices that cannot be deleted by Property 1. The sparser the graph is, the more vertices in the induced graph can be deleted. Therefore, efforts will be promoted for sparse graphs.

3.2 Graph Reduction Algorithms

With the graph reduction properties presented above, we propose several reduction algorithms. The first one, we call vertex-reduction, is based on Property 1. The detailed description of vertex-reduction is shown in Algorithm 1.

Algorithm 1: function vertex-reduction(G, LB, k)

Input: G = (V, E), k the k-plex parameter, LB a lower bound Output: G the reduced graph 1 Q← ∅; 2 foreach vertex v in V do 3 if dG(v) + k ≤ LB then add v into Q; 4 while Q is not empty do 5 v ← pop a vertex in Q; 6 foreach u in NG(v) do 7 if dG(u) + k - 1 ≤ LB then add u into Q; 8 if v is in V then remove v fromG; 9 return G;

The second one employs Property 4 to reduce the graph by counting allowed vertices in induced subgraphs, so we call it subgraph-reduction, shown in Algorithm 2. Rather than vertex-reduction that reduces the graph to minimal, subgraphreduction only checks each vertex once. When it finds a vertex that can be removed, it reduces the graph and updates vertex degrees immediately and then checks the next vertex. Subgraph-reduction runs in O(|V |×(|V |+|E|)) time, so the efficiency may be increased if the graph is sparse.

Algorithm 2: function subgraph-reduction(G, S, LB, k, C)

Input: G = (V, E), S a k-plex in G (S ⊆ V ), k the k-plex parameter, LB a lower bound, C the vertex set to be checked satisfying C ∩ S = ∅ Output: G the reduced graph 1 foreach vertex v in C do 2 compute rG,S(u) by Eq. (1), for ∀u ∈ (NG(v) \ S) ∪ {v}; 3 G′′ (V ′′ ,E′′ )←G, and Q← ∅; 4 foreach u in NG′′ (v) \ S do 5 compute cG′′,S(u, v) by Eq. (2); 6 if cG′′,S(u, v) ≤ LB-|S| then add u into Q; 7 while Q is not empty do 8 u ← pop a vertex in Q; 9 H ← (NG′′ (u) ∩ NG′′ (v)) \ S; 10 if u is in V ′′ then remove u fromG′′ ; 11 foreach w in H do 12 update cG′′,S(w, v) by Eq. (2) ; 13 if cG′′,S(w, v) ≤ LB-|S| then add w into Q; 14 if |(NG′′ (v) ∪ {v}) \ S| + rG,S(v) ≤ LB-|S| then 15 remove v fromG; 16 break; 17 return G;

Similarly, according to Property 3, we present the reduction method called v-reduction in Algorithm 3. It can reduce vertices in the induced subgraph after a vertex v is selected. It works similar to subgraph-reduction, but it removes vertices from G directly, since vertices not satisfying Property 3 no longer makes efforts.

Algorithm 3: function v-reduction(G, S, LB, k, v)

Input: G = (V, E), S a k-plex in G (S ⊆ V ), k the k-plex parameter, LB a lower bound, v a vertex in S Output: G the reduced graph 1 compute rG,S(u) by Eq. (1), for ∀u ∈ (NG(v) \ S) ∪ {v}; 2 Q← ∅; 3 foreach u in NG(v) \ S do 4 compute cG,S(u, v) by Eq. (2); 5 if cG,S(u, v) ≤ LB-|S| + 1 then add u into Q; 6 while Q is not empty do 7 u ←pop a vertex in Q; 8 H ← (NG(u) ∩NG(v)) \ S; 9 if u is in V then remove u fromG; 10 foreach w in H do 11 update cG,S(w, v) by Eq. (2); 12 if cG,S(w, v) ≤ LB-|S| + 1 then add w into Q; 13 return G;

Beside those methods, a strategy to deal with vertices violating the k-plex constraint is introduced here. If we aim at finding a k-plex including S, two kinds of vertices should be removed: 1) if there is a vertex u in S satisfying |S \ NG(u)| + 1 = k, then all vertices in V \ (NG(u) ∪ S) should be removed; 2) if there is a vertex u in V \S satisfying |S \NG(u)|+1 > k, then u should be removed. Algorithm 4 formally describes how to reduce the graph using the strategy above.

Algorithm 4: function k-reduction(G, S, k)

Input: G = (V, E), S a k-plex in G (S ⊆ V ), k the k-plex parameter, LB a lower bound Output: G the reduced graph 1 foreach u in S satisfying |S \NG(u)| +1 = k do 2 remove any w in V \ (NG(u) ∪ S) from G; 3 foreach u in V \ S satisfying |S \NG(u)| +1 > k do 4 remove u from G; 5 return G;

4 Preprocessing

As we know, massive graphs may have numerous nodes, which may cause the execution of an algorithm out of memory. So preprocessing is a necessary step, which can usually reduce the input graphs to a reasonable size. The more nodes in the original graphs are removed, the less branches are exploited in the searching algorithm. Algorithm 5 shows the procedure of the preprocessing step. We employ a heuristic method to obtain a lower bound, which is an extension of the method in [Jiang et al., 2017]. Based on the lower bound, vertex-reduction can reduce graphs efficiently due to its linear computation time for checking a vertex. However, the effectiveness, unfortunately, is not satisfactory, if the heuristic method fails to find a lower bound close to the optimal value.

It is not surprise that a heuristic sometimes finds a solution far from the best one. As a result, subgraph-reduction is also used in preprocessing for a further reduction. With the same lower bound, it can remove more vertices, though it needs higher computation complexity. Two reduction methods are preformed alternatively until no vertex can be removed. During iterations, the lower bound is updated before each execution of the vertex-reduction, since the heuristic may find new lower bounds when the graph is reduced.

Algorithm 5: function reduce-graph(G,k)

Input: G = (V, E), k the k-plex parameter. Output: LB a lower bound, and G the reduced graph 1 m ← |V | + 1,LB ← 0; 2 while |V | <mdo 3 m← |V |; 4 if LB-heuristic(G, k) > LB then 5 LB ← LB-heuristic(G, k); 6 G←vertex-reduction(G,LB, k); 7 G← subgraph-reduction(G, ∅,LB, k, V ); 8 return (LB, G); 9 function LB-heuristic(G, k); 10 for i ← 1 to |V | do 11 v ← the vertex with the smallest dG(v) in V ; 12 if dG(v) + k ≥ |V | then break; 13 remove v fromG; 14 return |V |;

5 The Branch-and-Bound Algorithm

In this section, we present our branch-and-bound algorithm. The entire framework of the algorithm is indicated in Algorithm 6.

The algorithm starts with the preprocessing algorithm to reduce the input graphs, and then it performs the branch-andbound algorithm. Search tree nodes are expanded recursively by the function BB. It returns the size of S if there is no vertex left, or the best lower bound found in its branch. There are some crucial components in the function BB to be explained.

The first one is the reduction methods. The branching rule here is binary, i.e., selecting a vertex and adding it into the target k-plex or discarding the vertex. After that, reductions are performed to simplify the remaining graph. Two combinations of reduction methods are employed after selecting and discarding, respectively.

In a selecting branch, we take three reduction methods. They are performed in the ordering of k-reduction, vertexreduction and v-reduction. The reason of taking this ordering is under the following observation: vertex-reduction cannot make efforts if performed first as it is irrelevant with S, but k-reduction can delete all conflict vertices directly. Therefore k-reduction is the first, and then vertex-reduction and v-reduction. Different from the preprocessing step, vreduction is employed instead of the subgraph-reduction due to the efficiency. In a discarding branch, vertex-reduction and subgraph-reduction are used. Obviously, k-reduction

Input: G = (V, E), k the k-plex parameter. Output: the size of the maximum k-plex 1 S ← ∅; 2 (LB,G) ← reduce-graph(G, k); 3 LB ←BB(G, S, k,LB); 4 return LB; 5 function BB(G, S, k,LB); 6 if V \ S is empty then return |S|; 7 select a vertex v in V \ S, and S ← S ∪ {v}; 8 store G as Gr; 9 G←k-reduction(G, S, k); 10 G←vertex-reduction(G,LB, k); 11 G←v-reduction(G, S,LB, k, v); 12 if |{u|u in V \ S and dG(u) +k > LB}| + |S| > LB then 13 lower ← BB(G, S, k, LB); 14 if LB < lower then LB ← lower; 15 restore Gr to G; 16 S ← S \ {v}, and remove v from G; 17 G←vertex-reduction(G,LB, k); 18 G← subgraph-reduction(G, S,LB, k, V \ S); 19 if |{u|u in V \ S and dG(u) +k > LB}| + |S| > LB then 20 lower ← BB(G, S, k, LB); 21 if LB < lower then LB ← lower; 22 return LB;

could not work in this branch, since S does not change after discarding a vertex so as to rG,S(v). However, the fact that degrees of discarded vertex's neighbors decrease makes vertex-reduction work well. To further enhance the reduction, subgraph-reduction is performed after vertex-reduction. Different from reducing graphs iteratively, all reductions are performed only once after selecting or discarding.

The second component discussed is the computation of upper bounds. After reductions, the algorithm should compute upper bounds to determine selecting a new vertex or trying another branch. Since the graph is reduced deeply, a simple but efficient method that counts the number of remaining vertices is developed for the upper bound, but the actual number of remaining vertices is not used as the bound directly in our algorithm. This is because the reduction methods during branch-and-bound searching are not performed iteratively, as we described above, and thus some vertices in a reduced graph may still satisfy the vertex-reduction rule. Therefore, we have to scan the vertices again to calculate the bound. To speed up this task, we employ a lazy method to determine whether the current branch has an upper bound bigger than the lower bound, rather than the method computing the exact value of the upper bound. This is achieved by counting remaining vertex whose degree exceeds the lower bound plus k. If it finds more than LB such vertices, the algorithm executes the function BB; otherwise, it tries the other branch or backtracks to the previous level.

The last one is the vertex selection heuristic, which specifies how to select a vertex on each node of the search tree. As we know the ordering of vertex selection may impact greatly on the search tree size. To make the selection mechanism effective, a dynamic vertex ordering strategy is employed in our algorithm. It selects a vertex according to the current branch and the remaining graph. The purpose of the dynamic vertex ordering strategy is to delete vertices as many as possible in the reduction after a selection. As the reduction algorithms are mainly based on vertex degrees, it is clear that selecting the vertex with the maximum degree from the remaining graph is a basic strategy that can decrease vertex degrees in full measure. Furthermore, our reduction method k-reduction is according to the value rG,S(v), the maximal allowed nonneighbors from the remaining graph, and thus if a vertex v with rG,S(v) = 0 is selected, all its non-neighbors can be removed. So a compound measurement is proposed, where rG,S(v) = 0 is the primary condition while the degree is the secondary condition used to break ties.

With the discussion above, two ordering rules are considered in our algorithm.

Rule 1. Select the vertex v with the maximum dG[V \S](v).

Rule 2. Select the vertex v with the maximum dG[V \S](v) from V0 = {v|k = |S\NG(v)|+1} if V0 is not empty; Select the vertex according to Rule 1 otherwise.

If there is more than one vertex as candidates, select the first one in lexicographical order. We call the BnB with Rule 1 as the vertex selection strategy BnBd, and the BnB with Rule 2 BnBk. In the following section, we will show comparative results of the exact algorithm we proposed.

6 Experiments

In this section, we performed intensive experiments to evaluate the algorithm we proposed. Two benchmarks were considered. One is selected instances from DIMACS benchmark, tested in [Xiao et al., 2017]. The other is real-world massive graphs, originally from the Network Data Repository online [Rossi and Ahmed, 2015], where 139 massive sparse graphs are selected 1 . Those benchmarks are popular on evaluating various massive graph algorithms [Rossi and Ahmed, 2014; Cai, 2015; Lin et al., 2017].

Our algorithms were implemented in C++ language and compiled by g++ version 4.7 with -O3 option. Benchmarks were solved parallel on a workstation with an Intel Xeon E5-1650v4 (3.6GHz) CPU, and 16GB RAM, running Ubuntu Linux 16.04, with the cutoff time 10000s. There are several exact algorithms proposed for the maximum k-plex, such as IPBC [Balasundaram et al., 2011], GuidedBranching [Moser et al., 2012] and BS [Xiao et al., 2017].

We first compare our algorithms with the three algorithms on DIMACS benchmarks fixing k = 2. Table 1 indicates runtimes, where "-" means time out or out of memory. BS and our algorithms are computed by our workstation whereas data of others come from [Xiao et al., 2017], which were computed by slower machines. From Table 1, it can be seen that IPBC is faster than others on hamming and johson instances, but those instances are relatively small. BS, BnBd and BnBk are good at solving instances with more than 200 vertices, such as c-fat500, brock and p hat instances. This result is compatible with [Xiao et al., 2017], in which it is reported that BS outperforms others on large instances (e.g. social networks). Among BS, BnBd and BnBk, BnBk performs best on most instances.

1 available at: http://lcs.ios.ac.cn/˜caisw/Resource/realworld%20 graphs.tar.gz

Consequently, we compare our algorithms with BS on massive graphs in the followings. It is noted that benchmarks from the Network Data Repository online includes many graphs with millions of vertices, which are much larger than the social networks (10 thousand vertices at maximum) used in [Xiao et al., 2017].

Before analyzing runtimes on massive graphs, we show the effect made by our subgraph-reduction. We count the remaining vertices in the preprocessing step compared to the method with vertex-reduction only (removing subgraphreduction from function reduce-graph). Detailed results of the facebook networks with k = 2 and k = 5 are listed in Table 2. It shows that using subgraph-reduction can remove much more vertices compared with using vertex-reduction only. In fact, the preprocessing function reduce-graph can reduce to 0.15% scale of the original graphs on average of 139 instances when k = 2, about 1/20 size of the vertex-reduction results. Surprisingly, it can reduce 68 out of 139 graphs to empty and thus achieved the maximum solutions without the branch-and-bound search. Moreover, similar results can be achieved when k =3,4,5.

Table 3 indicates statistic results grouped by families with k =2,3,4,5, respectively, by counting the successfully solved instances of three algorithms: BS, BnBk and BnBd. We use family abbreviations in the table, and full names are biological networks, collaboration networks, Facebook networks, interaction networks, infrastructure networks, amazon recommend networks, retweet networks, scientific computation networks, social networks, technological networks, temporal reachability networks and web link networks.

From Table 3, it is easy to see that BnBk solves the most amount of instances among the three algorithms, much more than BS. For each k, BnBk also performs best. Indeed, most instances solved by BS can also be solved by BnBk successfully, except only 7 instances partly due to unsatisfactory lower bounds obtained. In contrast, BS fails to solve some instances that can be solved by BnBk very easily, or saying within 100s. Also, BnBd reveals better performance than BS, but solves a bit fewer instances than BnBk. Moreover, the number of solved instances decreases with k growing for each algorithm, because most instances become harder to solve.

We then analyze runtimes. We only show solved instances with more than 50000 vertices, and thus select out 44 instances. Table 4 indicates runtimes with k=2,5, respectively, where "-" means time out or out of memory. It shows that BnBd and BnBk are much faster than BS on most instances; BnBd is slightly better than BnBk if instances can be solved in a short time; but BnBk shows a distinct advantage when instances are hard to solve, i.e., larger than 100s.

We also compare our BnBk with BS on the reduced instances. Specifically, we reduce benchmark instances with our preprocessing method, and then solve the reduced instances by both algorithms. Runtimes excluding preprocessing time are listed in Table 5, where instances solved within 10s and unsolved instances are omitted. From it, we can see BS is greatly improved when combining our preprocessing method as more instances can be solved than the original BS. Among 27 instances, BnBk performs better on 18 instances whereas BS on 9 instances. In total, BnBk is also better than BS when BS is associated with our preprocessing method.

7 Conclusions

To solve maximum k-plexes exactly, we have proposed a branch-and-bound algorithm for massive sparse graphs.

Three main components have been described in detail. Special graph reduction methods for sparse graphs have been proposed to enhance the efficiency of the algorithm, where analyzing of induced subgraph structures makes significant effects. Moreover, a dynamic vertex selection mechanism has been proposed to speed up searching. Additionally, a lazy computation of the upper bound has been introduced. Besides, a preprocessing method with our reduction strategies has been introduced in the algorithm, which may always reduce massive graphs to tractable sizes. We have shown our reduction strategies work effectively through computational experiments, and our algorithm outperforms the state-of-theart exact algorithms. It is also worth to mention that the graph with more than 50 million vertices can be solved in a very short time by our algorithm. In the future, parallelization of the proposed methods and algorithms for maximum weighted k-plex problems are valuable research directions.

Acknowledgments

We are grateful to the anonymous reviewers for their constructive comments which have helped us to significantly improve the paper. This work was supported by National Natural Science Foundation of China (Grant Nos. 61672122, 61503074, 61402070, 61370156, and 61602077).