Uncovering the Largest Community in Social Networks at Scale

1 Introduction

The largest community discovery is an essential tool to understand user behaviors in social networks [Shiokawa et al., 2013; Shiokawa et al., 2019]. To this end, traditional applications employ the maximum clique search [Tomita and Seki, 2003] or the maximum k-core search [Seidman, 1983]. However, these searches are difficult to apply to real-world social networks for two reasons. First, social networks have diverse densities due to the scale-free and the power-law properties [Faloutsos et al., 1999]. Second, the identified subgraphs using the above search methods tend to be too dense for actual communities [Matsugu et al., 2021]. Consequently, these methods fail to reproduce the largest community in realworld social networks [Pattillo et al., 2013].

To overcome these limitations, the Maximum k-Plex Search (MPS) [Balasundaram et al., 2007] has recently attracted much attention in the AI community [Conte et al., 2017; Conte et al., 2018]. MPS finds the maximum k-plex, which is the largest subgraph containing n nodes where each node is adjacent to at least n - k nodes within the subgraph [Seidman, Stephen B and Foster, Brian L, 1978]. Unlike traditional methods, MPS can balance the density and the size of a discovered subgraph to meet the diverse density of communities in social networks [Leskovec and Krevl, 2014]. As described below, MPS has recently been applied in various AI-powered applications:

Criminal network analysis: MPS effectively uncovers suspicious communications among terrorist cells, criminal gangs, and religious cults in social networks. For example, Wiil et al. applied MPS to public social network data to detect terrorist groups engaged in the September 11 attacks on the World Trade Center in 2001 [Wiil et al., 2010]. MPS uncovered more terrorists than other dense subgraph models. Similarly, MPS achieved a better performance in detecting narcotics trades and money laundering in criminal networks than the maximum clique model [Balasundaram, 2007].

Personalized social search: MPS can enhance a personalized social search, which reranks Web search results based on friendship communities in social networks [Noll and Meinel, 2007; Carmel et al., 2009]. Danezis et al. proposed an MPSbased algorithm that estimates search preferences shared in the largest friendship community [Danezis et al., 2010]. The algorithm first extracts the maximum k-plex from a social network. It infers preferences in the k-plex via Bayesian models. Their MPS-based algorithm achieved more accurate search results than other dense subgraph models.

Graph neural network (GNN): MPS contributes to enhanced performances of GNN which has played a key role in social network analysis. In GNN, graph pooling is essential to capture the context of nodes, and many clique-based methods have been used [Ying et al., 2018; Lee et al., 2019; Wang et al., 2020]. Bianchi et al. recently proposed an MPSbased graph pooling method [Bianchi et al., 2020]. They reported that the MPS-based method successfully mitigated the oversmoothing issues in GNN [Li et al., 2018], improving the accuracy compared to other GNN models.

MPS can also be used in other applications such as viral marketing [Doerr et al., 2012; Bodaghi and Oliveira, 2022], disease propagation analysis [Wang et al., 2003; Wang and Dai, 2008], etc. Due to space limitations, we omit the details here.

Although MPS is effective for many AI-powered applications, it has an NP-hard complexity [Balasundaram et al., 2007]. Specifically, the na¨ıve MPS algorithm requires O(2|VG| |VG|) time to find the maximum k-plex [Balasundaram et al., 2007], where VG is a node set. In the 2010s, MPS was applied to graphs composed of only 100 nodes. By contrast, recent AI-based applications handle massive graphs with at least 10,000 nodes [Jiang et al., 2021]. Hence, MPS requires several days to obtain the maximum k-plex.

1.1 Existing Approaches and Challenges

Many studies have improved the efficiency of MPS [Conte et al., 2018; Zhu et al., 2020]. Here, we focus on those most related to this study. For a broader discussion, please refer the Section 5. Classical algorithms include greedy branching [Moser et al., 2012], branch-and-cut [Balasundaram et al., 2007], and branch-and-search [Xiao et al., 2017]. To improve the efficiency, these algorithms attempt to reduce candidates of the maximum k-plex by bounding the k-plex size. Although they are faster than the na¨ıve MPS algorithm, quickly computing graphs with 10,000 nodes remains a challenge since they must explore numerous nodes due to the large search space. Hence, classical MPS algorithms fail to output the maximum k-plex in a reasonable time.

Gao et al. recently proposed branch-and-bound (BnB) as an alternative [Gao et al., 2018]. The key idea of BnB is to avoid unnecessary searches using graph reduction algorithms, which remove nodes that are unlikely to be the largest k-plex. Based on these reduction algorithms, BnB achieves a faster search than the classical ones. However, BnB still requires expensive costs to handle massive graphs due to insufficient node removal. To overcome this issue, several algorithms have introduced heuristic upper bounding methods [Zhou et al., 2021; Jiang et al., 2021; Chang et al., 2022]. Unfortunately, they are also unsuitable for large social networks since their graph reduction algorithms must scan the whole graph repeatedly. For example, the state-of-the-art method [Chang et al., 2022], incurs O(|VG|2 ) time to reduce the graph size. Thus, it is still a challenging task to develop an efficient MPS algorithm for massive social networks.

1.2 Our Approaches and Contributions

Our goal is to develop an efficient MPS algorithm for large social networks with million-scale nodes. Here, we present a novel algorithm called Branch-and-Merge (BnM). The existing approaches discussed in Section 1.1 suffer from a quadratic cost against the number of nodes since they must repeatedly scan all nodes to reduce the graph size. In contrast, the basic idea underlying BnM is to reduce the graph size by scanning only unpromising nodes. In social networks, many nodes are not included in the maximum k-plex due to the well-known scale-free property. Since BnM can efficiently reduce the graph size by removing unpromising nodes, it avoids redundant iterative traversals of all nodes.

We derived BnM using three steps: First, we theoretically derive safe-to-merge nodes, which are never included in the maximum k-plex together. (Section 3.2). Second, we provide a node-merging strategy to efficiently find safe-tomerge nodes (Section 3.3). Finally, we propose BnM using a node-merging strategy to efficiently find the maximum k-plex (Section 3.4). Furthermore, we theoretically show that the proposed node-merging strategy more efficiently reduces the graph size than state-of-the-art graph reduction algorithms. As a result, BnM has the following attractive characteristics:

• Efficiency: BnM is faster than recently proposed MPS algorithms (Section 4.1). BnM has a better time complexity than the state-of-the-art methods (Theorem 1).
• Exactness: BnM always outputs the maximum k-plex because it does not sacrifice the search quality of MPS algorithms (Theorem 2).
• Scalability: BnM is more scalable than other MPS algorithms (Section 4.3). BnM shows nearly linear scalability against the number of nodes in a graph.

BnM is the first solution that achieves an efficient and exact MPS on massive social networks. BnM outperforms other state-of-the-art MPS algorithms in terms of running time. For example, BnM finds the maximum k-plex from a scale-free graph that has 1.1 million nodes within 7 seconds, while the state-of-the-art algorithm [Chang et al., 2022] does not output a result within 100 seconds. Therefore, BnM can improve the quality in a wide variety of AI-based applications.

2 Preliminaries

First, we define the basic notations used in this paper. Table 1 summarized the main symbols and their definitions. Similar to previous studies [Gao et al., 2018; Zhou et al., 2021; Jiang et al., 2021], let G = (VG, EG) be an unweighted, undirected, and connected graph, where VG and EG are sets of nodes and edges in G, respectively. The degree of node u in G is denoted as dG(u). G[VS] represents an induced subgraph of G, where VS ⊆ VG. G-v is defined as the remaining graph after removing node v fromG ( i.e., G-v = G[VG\{v}] ).

MPS is a task to find the largest k-plex in a graph G, where k-plex is a generalization of a clique proposed by [Abello et al., 2002]. Formally, k-plex is defined as:

Definition 1 (k-plex). Given a graph G, and a positive integer k, a subgraph G[VS] ⊆ G is a k-plex if dG[VS](v) ≥ |VS| - k for all v ∈ VS.

If G[VS] is a k-plex, then each node v ∈ VS is adjacent to at least |VS| - k nodes. Thus, the MPS is defined as:

Problem 1 (MPS). Given a positive integer k, MPS is a task to find a k-plex G[VS] ⊆ G that maximizes |VS|.

If k = 1, Problem 1 is clearly equivalent to the maximum clique search [Bomze et al., 1999]. Since MPS is NP-hard [Abello et al., 2002; McClosky and Hicks, 2012; Xiao and Kou, 2017], an efficient algorithm must be developed to compute large social networks.

3 Branch-and-Merge (BnM)

This paper proposes BnM to efficiently find the maximum kplex. In this section, we overview the ideas underlying BnM and then provide a full description.

3.1 Overview

The existing approaches discussed in Section 1.1 iteratively run graph reduction algorithms to remove the unpromising nodes. These reduction algorithms require a quadratic cost against the number of nodes since all nodes are scanned repeatedly. In contrast, BnM can efficiently reduce the graph size by scanning the unpromising nodes. Herein, we first theoretically identify safe-to-merge nodes, which are not included together in the maximum k-plex (Section 3.2). We then introduce a node-merging strategy to efficiently remove the safe-to-merge nodes from a graph (Section 3.3). Finally, we describe BnM to drastically reduce the graph size and efficiently explore the maximum k-plex (Section 3.4).

Our ideas have two advantages. First, BnM is more efficient than existing approaches that repeatedly scan all nodes. Social networks contain many unpromising low-degree nodes due to the scale-free property [Faloutsos et al., 1999]. Because BnM scans only adjacent nodes for each unpromising node to reduce the graph size, it can drastically decrease the graph size on social networks. Second, BnM always outputs exact results, although it removes unpromising nodes via a node-merging strategy. This is because BnM detects nodes not included in the maximum k-plex while performing node merging. Hence, BnM does not sacrifice the k-plex search quality. Consequently, BnM can efficiently find the exact maximum k-plex included in massive social networks.

3.2 Safe-to-merge Nodes

BnM reduces the graph size by removing nodes not included together in the maximum k-plex. We call such nodes safe-tomerge nodes. To theoretically derive the safe-to-merge nodes, we introduce Definitions 2, 3, and 4:

Definition 2 ((α, k)-plex). A subgraph G[VS] ⊆ G is an (α, k)-plex in a graph G if G[VS] is a k-plex such that |VS| = α.

The (α, k)-plex is a k-plex whose size is α. For a given α, a graph can have multiple (α, k)-plexes. For instance, the graph in Figure 1 (a) has two (6, 3)-plexes: {v1, v2, v3, v4, v5, v6} and {v4, v5, v6, v7, v8, v9}.

Based on Definition 2, unfruitful nodes, which cannot be included in any (α, k)-plexes, are defined as:

Definition 3 (Unfruitful Nodes). For α and k, unfruitful nodes UG are defined as UG = {v ∈ VG | dG(v) < α - k}.

Definition 3 indicates that unfruitful nodes have a degree less than α-k. From Definitions 2 and 3, they are never included in any (α, k)-plexes. In Figure 1 (a), the set of unfruitful nodes is UG = {v11} since dG(v11) = 2 < α - k = 3.

Unfruitful nodes can be removed from a graph G since they are not included in any (α, k)-plexes. Because the node degrees decrease after node removal, G can have additional unfruitful nodes. Thus, we define a converged graph, which is obtained after removing all unfruitful nodes in G.

Definition 4 (Converged Graph). For α and k, let G(i) be the i-th remaining graph after removing unfruitful nodes as

A converged graph ˆG is defined as ˆG = G[VG(i)\UG(i) ] such that UG(i) = ∅.

As shown in Definition 4, a converged graph ˆG has no unfruitful nodes for any (α, k)-plexes. Suppose that the graph in Figure 1 (a) is used to generate the converged graph for (6, 3)-plexes. Recall that it has unfruitful nodes UG = {v11}. Figure 1 (b) shows G(1) , which is the graph after removing UG from G. From Definition 3, G(1) also has a set of unfruitful nodes UG(1) = {v10}. Figure 1 (c) shows graph G(2) , which has no unfruitful nodes since all nodes have at least α - k = 3 neighbor nodes. Hence, G(2) is the converged graph (i.e., ˆG = G(2) ).

We finally derive the safe-to-merge nodes using Definitions 2, 3, and 4 as:

Definition 5 (Safe-to-Merge Nodes). Given two adjacent nodes u, v ∈ ˆG, nodes u and v are safe-to-merge nodes and denoted as u ↔ˆG v, iff u ∈ U ˆG-v and v ∈ U ˆG-u .

Definition 5 indicates that node u becomes an unfruitful node after removing node v from ˆG if and only if u ↔ˆG v holds, and vice versa. In Figure 1 (c), the bold line links the safe-tomerge nodes. For example, two adjacent nodes v7 and v8 are the safe-to-merge nodes for (6, 3)-plexes because the degree

Algorithm 1 Node-merging algorithm

Input: A converged graph ˆG;

Output: A graph G∗ after merging safe-to-merge nodes;

1: procedure MERGE ( ˆG, α, k): 2: G∗ ← ˆG; 3: FG∗ ← {v ∈ VG∗ | dG∗(v) = α-k}; 4: M ←a connected node set in G[FG∗]; 5: while M ̸= ∅ do 6: Add a supernode s to VG∗ ; 7: for each v ∈ M do 8: for each u ∈ N(v)\M do 9: Add an edge (u, s) to EG∗ ; 10: Remove v from VG∗ ; 11: FG∗ ← FG∗ ∪ {s}\M; 12: M ← ∅; 13: for each v ∈ NG∗ (s) do 14: if v ↔G∗s then 15: M ← M ∪ {v}; 16: if M = ∅ then 17: M ← a connected node set in G[FG∗ ]; 18: return G∗ ;

of node v7 becomes 2 in G-v8 , which is smaller than α-k = 3. Additionally, node v8 has a degree smaller than 3 in G-v7 . For Definition 5, we derive the following lemma:

Lemma 1. For u ↔ˆG v, node u is not included in an (α, k)-plex if node v is not included in the (α, k)-plex.

Proof. We prove by contradiction. Given safe-to-merge nodes u ↔ˆG v, we assume that u is included in an (α, k)- plex if v is not included in the (α, k)-plex. That is, we have u /∈ UˆG-v . From Definition 5, this is a clear contradiction since u ↔ˆG v ⇒ u ∈ U ˆG-v holds. This completes the proof of Lemma .

Lemma 3.2 indicates that safe-to-merge nodes never become members of an (α, k)-plex if one of them is not included in the (α, k)-plex. Conversely, they are members of an (α, k)-plex if one is included in the (α, k)-plex. Thus, removing the safeto-merge nodes can effectively reduce the graph size if one of them is not included in the (α, k)-plex. However, it needs O(|V ˆG|2 ) time to list the safe-to-merge nodes for exploring all node pairs. To avoid this, we propose a node-merging strategy that dynamically merges unnecessary nodes.

3.3 Node-merging Strategy

We introduce a node-merging strategy to efficiently find safeto-merge nodes from a converged graph. We overview a key property underlying our strategy and then provide its details.

Node-merging Property To find the safe-to-merge nodes efficiently, we present the node-merging property. First, we define fragile nodes for a converged graph ˆG as:

Definition 6 (Fragile Nodes). Given a converged graph ˆG, fragile nodes F ˆG are defined as:

In Figure 1 (c), fragile nodes are those whose degree is α-k = 3. Thus, ˆG has FˆG = {v1, v2, v3, v7, v8}. Fragile nodes become unfruitful if one of their adjacent nodes is removed since the removed node decreases the degree of the fragile nodes. In Figure 1 (c), v7 is unfruitful after removing v8 from ˆG. Formally, safe-to-merge nodes can be obtained from G[F ˆG] using the following property:

Lemma 2. Let G[F ˆG] be the induced subgraph comprised of fragile nodes. If a path v1 → v2 → ... → vN exists in G[F ˆG], vi ↔ˆG vi+1 always holds for i ∈ {1, 2, ..., N - 1}.

Proof. From Definition 5, d ˆG(vi+1) = α- k holds. If vi is removed from ˆG, we have d ˆG-vi (vi+1) = α - k - 1 since (vi, vi+1) ∈ E ˆG. From Definition 3, we have vi+1 ∈ U ˆG-vi . Furthermore, vi ∈ UˆG-vi+1 holds since we have d ˆG(vi) = α - k. Hence, vi ↔ˆG vi+1 holds from Definition 5. If nodes are connected in the induced subgraph composed of fragile nodes, they are safe-to-merge nodes. In Figure 1 (c), nodes v1, v2, and v3 are included in FˆG. Because there is a path of v1 → v2 → v3 in G[FˆG], v1 ↔ˆG v2 and v2 ↔ˆG v3 hold. Clearly, we can find the path in O(|V ˆG|) time, at most, by obtaining the fragile nodes. Hence, Lemma 2 can be used to efficiently find safe-to-merge nodes.

Node-merging Algorithm Our algorithm efficiently finds safe-to-merge nodes by initially enumerating all safe-tomerge nodes based on Lemma 2. Then the nodes are removed based on Lemma 3.2 by merging the nodes to a supernode. This efficiently reduces the graph size. Here, we formally define a supernode as:

Definition 7 (Supernode). Given a graph ˆG and a set of connected safe-to-merge nodes M ∈ G[FˆG], a supernode s is defined as a node obtained after merging nodes in M. Here, s is adjacent to nodes in {v ∈ V ˆG | ∀u ∈ M, (u, v) ∈ EˆG}. We also define its degree d ˆG(s) as α - k. By merging M, nodes of M and edges linked to them are removed from ˆG. |s| = |M| denotes the number of merged nodes.

A supernode is a special class of nodes in which safe-tomerge nodes are represented as a single node. The degree of a supernode is always α - k since all merged nodes are fragile nodes. Additionally, a supernode can be linked by several edges since edges in M are reconnected to the supernode. For example, in Figure 1 (d), two edges (v1, v4) and (v2, v4) are reconnected as (s123, v4) after merging {v1, v2, v3} to s123.

If u, v ∈ FˆG are connected in G[FˆG], they are safe-tomerge nodes based on Lemma 2. Using this property, Algorithm 1 is designed to output a graph after merging the nodes by finding the safe-to-merge nodes in ˆG. Algorithm 1 first constructs fragile nodes FG∗ . Then it finds a connected node set M in G[FG∗] using depth-first-search (DFS) 1 based on Lemma 2 (lines 3-4). For each connected node set M, Algorithm 1 replaces M with the corresponding supernode s using Definition 7 (lines 6-10). Then it adds s to FG∗ since the degree of s is α - k (line 11). Let NG∗(u) = {v ∈ VG∗ | (u, v) ∈ EG∗} be a set of adjacent nodes of node u in G∗ .

1 Any search method is acceptable if it yields equivalent search results as DFS.

Input: A given graph G, a positive integer k; Output: A maximum k-plex Gmax; 1: ˆG←G, Gmax ← ∅, α← k +1; 2: while true do 3: Gcurr ←BRANCH ( ˆG, α, k); 4: if Gcurr = ∅ then 5: return Gmax; 6: ˆG ← G[V ˆG\F ˆG]; 7: Gmax ←Gcurr; 8: α←α+1; 9: 10: procedure BRANCH ( ˆG, α, k) 11: ˆG←a converged graph of ˆG for α and k; 12: n← 0; 13: for each v ∈ V ˆG do 14: if v is a supernode then 15: n ← n + |v|; 16: else 17: n ← n + 1; 18: if n = α then 19: return ˆG; 20: if n < α then 21: return ∅; 22: G∗ ←MERGE ( ˆG, α, k); 23: Gcurr ← ∅; 24: for each v ∈ VG∗ do 25: Gcurr ← BRANCH (G∗-v , α, k); 26: if Gcurr ̸= ∅ then 27: return Gcurr ; 28: return ∅;

Then Algorithm 1 updates the connected node set M by exploring the nodes in NG∗(s). If NG∗ has the safe-to-merge nodes to s, Algorithm 1 adds the nodes to M (lines 13-15). Otherwise, it explores another connected node set (lines 1617). Finally, Algorithm 1 is terminated if no safe-to-merge nodes are found (lines 5-17).

Figures 1 (c), (d), and (e) illustrate a running example of Algorithm 1. Figure 1 (c) shows that the converged graph ˆG has F ˆG = {v1, v2, v3, v7, v8}. By merging {v7, v8}, Algorithm 1 adds supernode s78 as shown in Figure 1 (d). Based on Definition 7, the edges (v7, v4), (v7, v9), (v8, v6), and (v8, v9) are replaced by (s78, v4), (s78, v9), (s78, v6), and (s78, v9), respectively. Then Algorithm 1 merges {v1, v2, v3} into s123. In Figure 1 (d), since s78 and v9 are linked by two edges, they become the safe-to-merge nodes by Definition 5. Hence, our algorithm merges them into s789 in Figure 1 (e), and the graph has no safe-to-merge nodes.

Finally, we theoretically assess the time complexity to merge all safe-to-merge nodes in ˆG using Algorithm 1.

Proof. Algorithm 1 can be split into two processes: finding the safe-to-merge nodes (lines 4, 12-17) and reconnecting the edges to merge the nodes (lines 5-9). We first discuss the time complexity to find all safe-to-merge nodes. As proved in Lemma 2, if a path exists in G[F ˆG], the nodes in the path are safe-to-merge nodes. Thus, we employ the depth-first search (DFS) to enumerate the connected node set in G[FˆG]. We start DFS from a fragile node in F ˆG to explore adjacent fragile nodes in ˆG recursively. If the search is terminated, the fragile nodes explored by the DFS are safe-to-merge nodes. By performing DFS iteratively by selecting unvisited fragile nodes as the starting node, we can enumerate all connected node sets in G[F ˆG]. This computation incurs O(|F ˆG| · (α-k)) time for two reasons. First, each fragile node has exactly α - k adjacent nodes in ˆG. Second, DFS is performed only for fragile nodes F ˆG and their adjacent nodes. Next, we discuss the time complexity to reconnect edges of the merging nodes. From Definition 5, each safe-to-merge node v ∈ M becomes an unfruitful node if nodes in M\{v} are removed from ˆG. Thus, v has less than α - k adjacent nodes in ˆG\M from Definition 3. It indicates that less than α-k edges are reconnected for each merged node. Since the number of merged nodes is approximately |FˆG| from Lemma 2, reconnecting edges incurs O(|FˆG| · (α - k)) time. Hence, Algorithm 1 needs O(|FˆG| · (α-k)) time in total.

As described in Section 3.1, real-world social networks typically contain many low-degree nodes due to the scale-free property; the expected number of nodes with d adjacent nodes is proportional to |VG|d-γ , where γ is a positive constant representing the strength of the degree skewness [Albert and Barab´asi, 2002]. Since fragile nodes are adjacent to exactly d = α - k nodes, we have O(|F ˆG|) ≈ O(|V ˆG|(α - k)-γ ) in practice. Thus, Algorithm 1 practically incurs O(|FˆG| · (α - k)) ≈ O(|V ˆG|/(α - k)(γ-1) ) time to reduce the graph size, which is a sublinear time to the number of nodes in realworld social networks. In contrast, existing state-of-the-art algorithms require O(|VG|2 ) time to reduce the graph size. Thus, Lemma 3 indicates that Algorithm 1 reduces the graph size more efficiently than state-of-the-art MPS algorithms.

3.4 BnMAlgorithm

Algorithm 2 fully describes BnM. It iteratively explores (α, k)-plexes by increasing α until the maximum k-plex is found (lines 2-8). Initially, BnM sets α = k + 1 since any k nodes can be a (k, k)-plex (line 1). In each iteration, BnM invokes the BRANCH function (line 3) to find (α, k)-plexes from ˆG. The BRANCH function is composed of two steps: (1) graph reduction (line 22) and (2) graph branching (lines 24-27). The first step reduces the graph size using the MERGE function shown in Algorithm 1, which finds and merges the safeto-merge nodes to efficiently reduce the graph size. In the subsequent step, BnM recursively invokes the BRANCH function by removing each node in VG∗ one-by-one (lines 24-25). After recursive computations, if the graph size of ˆG reaches α, ˆG is returned as an (α, k)-plex (lines 18-19). Otherwise, the BRANCH function outputs no graph (lines 20-21). Finally, BnM outputs (α - 1, k)-plexes as the maximum k-plex if the BRANCH function does not return a graph (lines 4-5).

Theoretical analysis: We theoretically assessed the efficiency and the exactness of BnM. By letting τ be the total number of BRANCH functions invoked in Algorithm 2, the time complexity of BnM is analyzed as follows:

Proof. As shown in line 22 of Algorithm 2, the BRANCH function invokes the MERGE function, which incurs O(|F ˆG|(α - k)) time, as proved in Lemma 3. Furthermore, as shown in lines 24-27 in Algorithm 2, BnM performs |V ˆG| iterations to explore (α, k)-plexes. Hence, BnM requires O(τ(|V ˆG| + |FˆG|(α-k))) time.

State-of-the-art MPS algorithms require O(|VG|2 ) time for each graph reduction. Thus, they incur O(τ|VG|2 ) time to find the maximum k-plex. In contrast, BnM drastically reduces the time complexity. Since O(|FˆG|) ≈ O(|VG|/(α - k)(γ-1) ) holds due to the scale-free property, we have O(τ (|VG|+|F ˆG|(α-k))) ≈ O(τ |VG|(1+1/(α-k)(γ-2) ))) for the time complexity as proved in Theorem 1. Since O(1 + 1/(α - k)(γ-2) ) ≈ O(1) in practice, BnM incurs O(τ|VG|) time. Because τ theoretically depends on |VG∗|, which dynamically decreases as the search progresses, the practical size of τ is much smaller than |V ∗ G|. Thus, BnM has an almost linear scalability against the number of nodes. In Section 4, we further assess the practical efficiency and scalability using real-world social networks.

We then assess the exactness of BnM as follows:

Theorem 2. BnM outputs the exact maximum k-plex.

Proof. BnM is composed of two steps: (1) construct ˆG (line 11) and (2) invoke the BRANCH function (lines 3, 1028). As shown in line 11 of Algorithm 2, ˆG is constructed while removing only unfruitful nodes not included in the (α, k)-plex from Definition 4. Second, as shown in lines 24-27 of Algorithm 2, BnM recursively searches (α, k)-plex from ˆG without v while varying v ∈ ˆG. As we proved in Lemma 1, if v is a member of a supernode s, then all nodes merged into s are never included in any (α, k)-plexes in ˆG-v, even if each node is not computed by Algorithm 2. That is, BnM does not fail to find all (α, k)- plexes in each iteration, although it simultaneously removes all nodes of the supernode by a node-merging strategy. Therefore, BnM outputs the exact maximum k-plex.

Theorem 2 indicates that BnM efficiently finds the exact maximum k-plex, although BnM dynamically prunes numerous nodes. As a result, BnM achieves an efficient MPS algorithm without sacrificing the quality of AI-powered applications.

4 Experimental Evaluation

We experimentally evaluated the efficiency of BnM.

Experimental Setup: We compared our proposed algorithm BnM with state-of-the-art MPS algorithms: BnB [Gao et al., 2018], Maplex [Zhou et al., 2021], KpLeX [Jiang et al., 2021], and kPlexS [Chang et al., 2022]. All experiments were conducted on a Linux server with Intel Xeon Gold 6246R CPU 3.40 GHz and 128 GiB RAM. All algorithms were implemented in C/C++ using "-O3" option as a single-threaded program with the entire graph held in the main memory. All results are averaged over ten independent runs.

Datasets: We tested 11 real-world social networks used in previous works [Gao et al., 2018; Zhou et al., 2021; Jiang et al., 2021; Chang et al., 2022] with more than 100,000 nodes, which are originally published by the Network Repository [Rossi and Ahmed, 2015] 2 . Table 2 shows their statistics, where αmax and γ denote the size of the maximum k-plex and the skewness of the degree distribution, respectively. If γ is large, the graph has many low-degree nodes.

4.1 Efficiency

Table 2 shows the running times of MPS on the datasets, where DNF indicates that the runtime exceeded 10,000 seconds. Similar to previous studies [Gao et al., 2018; Zhou et al., 2021], we varied k from 2 to 5. Although BnM guarantees the same results as the Na¨ıve algorithm by Theorem 2, it is up to 305.2, 311.0, 9.53, and 14.54 times faster than BnB, Maplex, KpLeX, and kPlexS, respectively. Specifically, BnM significantly outperforms the other methods on graphs with a large γ value (e.g., soc-lastfm, soc-pokec, soc-livejournal, etc.). Compared to other algorithms, BnM has an improved time complexity as proved in Theorem 1. It is responsible for the superior running time.

In many datasets, BnM can find the maximum k-plex even if k is set to 5, unlike the graph reduction algorithms of BnB, Maplex, KpLeX, and kPlexS. As k increases, the computation cost increases since the maximum k-plex would be large. Regardless of the degree distribution, the reduction algorithms repeatedly compute all nodes to remove unpromising nodes. However, real-world social networks have many low-degree nodes (i.e., large γ values in Table 2) that are unlikely to be the maximum k-plex due to the scale-free property. Thus, reduction algorithms fail to return the maximum k-plex for large k settings on massive graphs. In contrast, BnM efficiently removes unpromising nodes using a nodemerging strategy based on the scale-free property if graphs have a large γ value. Therefore, BnM can efficiently compute massive social networks with large k settings compared to other MPS algorithms.

4.2 Effectiveness

We experimentally evaluated the effectiveness of our approach by comparing the runtime of BnM to its variant that excludes the node-merging strategy (BnM (w/o merge)). Table 3 shows the runtimes, where DNF indicates the algorithm did not finish within 10,000 seconds. Table 3 also includes the graph reduction ratio (GRR), which is the fraction of edges visited by BnM compared to BnM (w/o merge), to visualize the reduced graph size by the node-merging strategy.

2 All graphs are publicly available online from https://networkrepository.com.

On average, BnM reduces the running time by 99.96% compared to BnM (w/o merge). These results correspond to the values derived from GRR where the node-merging strategy reduces 99.93% of the computed edge sizes compared to BnM (w/o merge). These results indicate that the nodemerging strategy enhances the efficiency since BnM dramatically reduces the search space. Our strategy can remove all the safe-to-merge nodes simultaneously if one of them is not included in the (α, k)-plexes (Lemma 3.2). Furthermore, the average number of GRR is 0.07%, which implies that the size of τ in Theorem 1 is quite small since the size of τ depends on the graph size obtained after merging safe-to-merge nodes G∗ . Consequently, the node-merging strategy effectively reduces the running time.

4.3 Scalability

We assessed the scalability of BnM. Figure 2 plots the running time on the four largest social networks in Table 2 as a function of the number of nodes. We sampled 1 × 104 , 3×104 , 1×105 , 3×105 , and 1×106 nodes from the original graphs using the Metropolis-Hastings Random Walk [Cui et al., 2022] and evaluated the runtime on each sampled graph with k = 5. If the algorithm did not finish within 10,000 seconds, the results are omitted in Figure 2.

Overall, BnM shows a nearly linear scalability against the number of nodes on most graphs due to the skewness of the degree distribution in social networks. BnM requires O(τ|VG|(1+1/(α-k)(γ-2) ) ≈ O(τ|VG|) time if γ is sufficiently large. Hence, BnM is scalable if a degree distribution is highly skewed. Therefore, BnM achieves a nearly linear scalability since most graphs have a large γ value (Table 2).

5 RelatedWorks

The problem of finding large dense communities has been studied for several decades [Matsugu et al., 2020; Shiokawa and Takahashi, 2020; Shiokawa, 2021]. Here we review some of more successful MPS methods.

MPS algorithms: MPS is a problem to find the largest k-plex included in a graph. MPS was first proposed by [Balasundaram et al., 2007] in 2007 as a generalization of a maximum clique search. However, the na¨ıve MPS algorithm is unresponsive to large social networks because it requires O(2|VG| |VG|) time, where |VG| is the number of nodes included in a graph [Balasundaram et al., 2007].

Several branching algorithms have been proposed to overcome this limitation. Examples include GuidedBranching [Moser et al., 2012] and BS [Xiao et al., 2017]. The key idea of these algorithms is to recursively partition search spaces explored during the search process by branching each search space according to whether a node can be included in the maximum k-plex or not. As reported in [Xiao et al., 2017], branching algorithms reduce the running times for graphs with 700 nodes. However, they still require an expensive cost to handle large social networks since the algorithms need O(1.98|VG| |VG|2 log(|VG|)) time for MPS at k = 5.

Recently, Gao et al. proposed branch and bound (BnB) to mitigate the expensive costs of MPS. To enhance the computational efficiency, BnB introduced graph reduction approaches that dynamically exclude unpromising nodes, which are unlikely to be the maximum k-plex. BnB approaches still incur a large computational cost to find unpromising nodes because they must repeatedly scan the whole graph. To mitigate the overhead of graph reduction approaches, several bounding methods have recently been proposed such as Maplex [Zhou et al., 2021], KpLeX [Jiang et al., 2021], and kPlexS [Chang et al., 2022]. These methods employ tighter upper bounds for graph reduction to further reduce the number of visited nodes/edges. However, these cannot handle large social networks with a few million nodes since their state-of-the-art approaches require O(|VG|2 ) time to exclude unpromising nodes.

Our work differs from these existing MPS algorithms in that BnM provides a very efficient graph reduction algorithm based on a node-merging strategy (Section 3.3). As we theoretically discussed in Section 3.4, BnM incurs O(τ|VG|)

time in practice, which is more efficient than the above algorithms. Furthermore, our experimental analysis in Section 4 shows that BnM has a higher performance in terms of the running time and the node-merging strategy successfully removes 99.93% of visited edges.

Other k-plex search algorithms: Several other types of kplex search problems have also been studied in recent years. An example is the maximal k-plex search [Wang et al., 2017; Conte et al., 2018; Zhou et al., 2020]. Given a user-specified query nodes VQ, the maximal k-plex search is a problem to find a k-plex GS such that GS includes all VQ and no other k-plex that contains GS exists. Unlike MPS, the maximal k-plex search is not guarantee to output the largest k-plex because it requires user-specified query nodes. Conversely, the maximal k-plex search algorithms can find the maximum k-plex if all possible query patterns can be tested, but this clearly incurs O(2|VG| ) time. Unfortunately, even state-ofthe-art algorithms [Dai et al., 2022] still require exponential complexity with the number of nodes. Thus, it is difficult to use a maximal k-plex search for MPS.

Unlike the above approaches, our proposed method, BnM, guarantees to output the maximum k-plex. Furthermore, we theoretically and experimentally verified that BnM has an almost linear scalability with the number of nodes included in a graph. That is, BnM is a more effective approach than the above ones in terms of the maximum k-plex finding.

6 Conclusion

Here, we propose an efficient MPS algorithm, BnM, for massive social networks. BnM effectively handles the scale-free property of social networks. It reduces the graph size by finding and merging safe-to-merge nodes. Experiments reveal that BnM offers an improved efficiency compared to state-ofthe-art MPS algorithms. Consequently, BnM can enhance the effectiveness of AI-powered applications for massive graphs.

Acknowledgements

This paper is partly supported by JST PRESTO JPMJPR2033, JST AIP Acceleration Research JPMJCR23U2, and JSPS KAKENHI 22J10972.