Influence-based community partition for social networks

Social network is an interdisciplinary research area which has attracted a lot of attention in recent years. One important problem in social networks is community partition that provides the insight of the relationships and attributes of the users that a social network comprises. Generally, a social network can be modeled as a graph in which the nodes represent the users and the edges represent the relationships among the users. The objective of community partition is to cluster the users into groups according to their graph topology [1]-[8]. Another important problem in social networks is influence propagation. It is one of the most important features of social communication and plays a significant role in a variety of affairs such as diffusion of medical innovations and popularization of new technologies. For example, the influence maximization problem, with the objective of finding a small set of users in a social network as seeds to trigger a large influence propagation, has wide applications in viral marketing [9]-[13].

Due to the nondeterminacy of human behaviors, the influence propagation is mostly studied in probabilistic models such as the Linear Threshold (LT) model and Independent Cascade (IC) model [14]-[16], that is, the behaviors and decisions of users are uncertain and depend on the behaviors of others. For example, a user’s adoption of a new product may have impacts on their friends, whose adoptions may further influence others. Therefore, probabilistic models are more suitable than deterministic models for simulating an influence propagation in social networks. Unfortunately, one important issue however is that the expected influence propagation through the entire social network is hard to estimate for most probabilistic models such as LT and IC [15],[16]. Therefore, many works (e.g., [15]-[17]) construct a local area for each user and use the local influence propagation instead of the global one. But in some large social networks, there may be millions of users so that it is impossible to construct local areas for all the users.

There are also many works studying community-based algorithms for influence maximization, assuming that influence propagates rarely across different communities. However, based on our observation, there are few works done on community partition aiming specially at influence propagation in social networks. The performance of community-based algorithms cannot be guaranteed unless there exists an accurate influence-based community partition. In this paper, we investigate the problem inherent in the question that how to partition a social network into disjoint communities in terms of influence propagation. We believe this study is useful for the influence maximization problem and possibly activates further research and potential applications of community in social networks.

Community partition is of great importance not only for social networks but also for areas such as computer networks and biology networks. There are lots of works done on community partition in general networks (e.g., [6],[8],[18],[19]), and much effort has been devoted to formalizing the intuition that a community is a set of nodes having more connections with each other while fewer connections with the remainder of the network. The first investigation for community partition were done by Weiss et al. [20]. For subsequent approaches, there are mainly four categories: hierarchy-based methods [1],[2], spectrum-based methods [3],[4], density-based methods [5] and modularity-based methods [6]-[8],[21]-[29]. Particularly, Newman’s notion of modularity [6],[8], which considers the internal connectivity with reference to a randomized model, has been a very popular measure for community partition in general networks. In spite of the excellent performance on many real-world networks, this family of approaches usually has ‘resolution limit’ problems, i.e., modularity-based methods favor larger communities and fail to discover communities of small sizes [25],[30]. Therefore some works investigate new methods for detecting communities, such as the self-reference methods and the comparative methods [18]. In addition, in [19], Hu et al. proposed an algorithm from the node’s point of view to incorporate nodes into a community with the largest attractive force. In [31], Zhang et al. proposed an algorithm from the aspect of combinatorial optimization to partition nodes into disjoint parts. There are also many works which view communities from different perspectives. To learn more about the large body of works in community partition, please refer to [29],[32]-[37].

Besides community partition, influence propagation is also an important issue in social networks. Domingos and Richardson in [13] and [12] first proposed general descriptive models for influence propagation in social networks. In [14], Kempe et al. formulated the influence propagation as an optimization problem, namely, influence maximization. They proved that the greedy algorithm has a provable performance guarantee for the LT and IC models. However, how to evaluate the expected influence propagation for selecting the nodes with the maximum marginal gain was left as an open problem, and the greedy algorithm in [14] was implemented by Monte Carlo (MC) simulation. After that many researchers started to investigate how to compute the influence propagation efficiently and a large volume of methods (e.g., [15],[16],[38]) have been proposed for the LT and IC models. Meanwhile, there are also many works investigating new influence propagation models (e.g., [39],[40]) to approach the real-world scenarios.

Due to the nature of the communities, applying the research of community partition into influence propagation is promising. In [17], Wang et al. proposed a community-based greedy algorithm for mining the most influential nodes. In [41], Li et al. further proposed an algorithm for influence maximization in online social networks. They assume that each node’s influence propagation is limited to the community it resides and thus they evaluate the influence propagation within each community to improve the computational efficiency. There are also many works for influence propagation or other social network applications taking the advantage of community structures (please see e.g., [42]-[45] for recent works).

Although there are a lot of works done on general community partition, based on our observation, there are few works done on community partition for influence propagation. In view of this, we investigate how to partition a social network into communities according to influence propagation. Our main contributions are as follows:

(K-VDP). Given a graph G(V,E) as a social network, a K-valid disjoint partition is a collection of K sets {C₁, C₂, …, C _K } satisfying: (1) ⋃ k = 1 K ( C k ) = V and (2) ∀i≠j, C _i ∩C _j =∅.

Let K be an integer no less than 2. According to Definition 1, a K-VDP is a partition of V into K nonempty subsets such that each node is in exact one subset. We denote the influence propagation function for a K-VDP {C₁, C₂, …, C _K } by f ( C 1 , C 2 , … , C K ) = ∑ k = 1 K σ ( C k ) and we want to maximize f(C₁, C₂, …, C _K ). The formal definition of MK CP is given in Definition 2.

(MKCP). Given a graph G as a social network, an influence propagation model (such as IC or LT) and an integer K≥2, Maximum K-Community Partition (MK CP) is the problem of finding a partition P = { C 1 , C 2 , … , C K } of K subsets of nodes,

Consider the node set V as a single community, we have

It is clear that when partitioning the social network into two or more communities, some pairs (i,j) will be separated and thus both p _V (i,j) and p _V (j,i) have to be removed in the sum of influence propagation. In addition, even though nodes i and j are partitioned into the same community X, p _X (i,j) may be less than p _V (i,j), and p _X (j,i) may be less than p _V (j,i) because X is a subset of V. Therefore, the influential propagation between any pair of nodes i and j is different for different community partitions no matter they are in the same community or not.

In this subsection, we present an optimal algorithm to M2CP for a class of influence propagation models. The algorithm is based on the Min Cut algorithm proposed in [46]. Before giving the formal algorithm and its theoretical analysis, we briefly discuss the difference between the Min Cut problem and the M2CP problem. A min cut of a graph G is a set of edges with the least number of elements (un-weighted case) or the least sum of weights (weighted case) that partitions G into two parts. On this basis, for M2CP, one may want to find a cut to minimize the influence propagation leaking out between the two parts. However, maximizing the sum of influence propagation within each community is not equivalent to minimizing the influence propagation crossing different communities. Figure 2 shows an example. There are eight nodes which are partitioned into two communities C₁={1,2,3,4} and C₂={5,6,7,8}. Assume the gray-directed arcs are the possible influence propagation. Consider nodes 7, 5, and 1, respectively. It is clear that the influence received by nodes 7 and 5 will decrease after the partition because node 3 cannot influence node 7 and it cannot influence node 5 via node 7 indirectly. The influence received by node 1 also decreases because of the following: (1) node 5 cannot influence node 1, (2) node 7 cannot influence node 1 indirectly, and (3) node 3 cannot influence node 1 through the path (3→7→5→1). The first two kinds of influence propagation are between nodes in different communities, but the last one is between nodes in the same community. Therefore, maximizing the sum of influence propagation within each community is not just minimizing the influence propagation crossing different communities.

Given a social network as well as an influence propagation model, our algorithm iteratively finds n−1 partitions and selects the one with the maximum value as the final output. In the beginning, we consider each node i as a single set and let V = { S 1 , S 2 , … , S n } as the collection of all the sets where S _i ={i}. Select an arbitrary set S i ∈ V and let A = { S i }. We then add the remainder sets one by one iteratively into . Each time a set S _j with the maximum value of ς ( A , S j ) is added, where ς ( A , S j ) = σ ( A ∪ S j ) − σ ( S j ). When there are only one set S _l left, { v ( A ) , v ( V ∖ A ) } are considered as the first partition where v ( X ) is defined as the set of nodes in . In addition, the last two sets not in , say S _r and S _l , are merged as a single set (S _r ∪S _l ) for computing the next partition. The algorithm terminates when there are only one set in . The pseudo-code is given in Algorithm 1.

The computational complexity of AM2CP (Algorithm 1) depends on the time complexity of computing σ(·), which further depends on the time complexity of computing the influence propagation p C k ( i , j ) for community C _k and all the pairs (i,j) of nodes in it. In [15], Chen et al. prove that it is # P-hard to compute the exact influence propagation in LT and IC models. Therefore, in this work, p C k ( i , j ) is estimated by MC simulation. Assume we have a simulator to estimate σ(·) in τ time. Following Algorithm 1, we run steps (3 to 11) n−1 times for the n−1 partitions. For each partition, we add all the sets greedily into that calls the function σ ( · ) O ( n 2 ) times. Therefore, the overall running time of AM2CP is O ( n 3 τ ).

We next show that AM2CP is an optimal solution for M2CP when the community influence propagation function σ(·) is super-modular. Let S be a finite set. A function f:2 ^S →R is super-modular if for any B⊂A⊂S and u∉A,

or equivalently for any B,A⊂S,

In this subsection, we study the hardness of MK CP. We show that the MK CP problem, with arbitrary K, is N P-hard in the LT or IC model.

In this subsection, we present two heuristic algorithms for MK CP. As mentioned in ‘Related work’ section in the literature, there are mainly four categories of methods for community partition: hierarchy-based methods, spectrum-based methods, density-based methods, and modularity-based methods. In our point of view, spectrum-based methods, density-based methods, and modularity-based methods are not suitable for MK CP. In spectrum-based methods, communities are partitioned by studying the adjacency matrix which cannot reflect the information of influence propagation. In density-based methods, communities are defined as areas of higher density than the remainder of the data set. Therefore, this category of methods requires the location knowledge of nodes which cannot be formulated in our MK CP problem. In modularity-based methods, the objective of community partition is only to maximize the global modularity score. Therefore, all the three categories of methods cannot be applied for MK CP and we focus on hierarchy-based methods.

Generally speaking, hierarchical community partition is a method to build a hierarchy of communities. There are two strategies for hierarchical partition. One is split and the other is merge. Split is a top down approach, i.e., all the nodes start within one community, and splits are performed on one of the communities recursively. Conversely, merge is a bottom up approach, i.e., each node starts in a distinct community, and pairs of communities are merged recursively as a new community. For typical hierarchical community partition problems, n−1 splits (or respectively merges) have to be done to build a hierarchy where n is the number of nodes. But for the MK CP problem, we need only K−1 splits or n−K merges respectively to obtain a K-VDP. We will determine the splits and merges in a greedy manner. The Split algorithm runs by calling AM2CP recursively, and each time it partitions a community X into two communities X₁ and X₂ with the minimum value of σ(X)−(σ(X₁)+σ(X₂)). The pseudo-code is given in Algorithm 2. The Merge algorithm runs by randomly selecting a community X each time and finding another community Y to maximize the value of σ(X∪Y)−(σ(X)+σ(Y)). The pseudo-code is given in Algorithm 3.

In the general case, the running time of a split with an exhaustive search requires exponential time. However, when σ(·) is super-modular, we can apply AM2CP to determine C z 1 and C z 2 for each C _z which requires only O ( | C z | 3 τ ) time. Now let us consider the computational complexity of SAMK CP (Algorithm 2). To avoid duplicate computations, we can keep the optimal partition for each community in and apply AM2CP on both C z 1 and C z 2 at step 4 to obtain their optimal partitions. Then the overall running time of SAMK CP is O ( K n 3 τ ) when σ(·) is super-modular.

In step 4 of MAMK CP (Algorithm 3), in order to maximize the marginal gain, we have to compute σ(C _i ∪C _j ) for all the communities C j ∈ P, thus, MAMK CP requires O ( n 2 τ ) time to obtain a K-VDP when n is large and K is small. The computational complexity of SAMK CP is even higher. Therefore, they may be not suitable for large social networks. To improve the running time performance, here we provide an alternative merge strategy for implementing MAMK CP. Instead of merging the communities with the maximum marginal gain, in step 4 we estimate the influence propagation of C _i through the entire graph, i.e., σ _V (C _i ), and then compute the average influence received by C _j from C _i , which is defined as ∑ l ∈ C i ∑ r ∈ C j p V ( l , r ) | C j |, for all the communities C _j ≠C _i . This can be done by simply accumulating p _V (l,r) for each community C _j when we computing σ _V (C _i ). Finally, we merge C _i with a community with the highest average received influence. In such a way, a merge can be done in O(τ) time. The overall running time of MAMK CP is only O ( nτ ).

According to the complexity analysis, MAMK CP is better than SAMK CP in terms of the running time performance. For some large social networks, we can apply the simplified version of MAMK CP which requires only linear time. In terms of the partition quality, intuitively, SAMK CP is better than MAMK CP because it considers the global optimization (top-down approach) each time and MAMK CP considers the local optimization (bottom-up approach). We will demonstrate their performance through simulation in the next section.

In addition to the proposed algorithms, (SAMK CP, Algorithm 2) and (MAMK CP, Algorithm 3), we also implement two classic community partition algorithms for comparison purposes. One is a Modularity-based Algorithm (MODUA) proposed in [47] and the other is a Spectrum-based Algorithm (SPECA) proposed in [48]. Given a graph G, MODUA finds communities by optimizing the modularity score locally and it terminates until a maximal modularity score is obtained. Therefore, MODUA cannot partition G into a given number K of communities. While SPECA is flexible for the number K of communities, it partitions a graph iteratively into K communities by minimizing the general cut each time according to the adjacent matrix. To the best of our knowledge, we do not find any algorithm which is designed for disjoint community partition with the objective of maximizing the influence propagation within each community. In addition, we do not find any density-based algorithm that can be applied to our MK CP problem.

We conduct simulation on three real-world social networks as follow: (1) NetHEPT: taken from the co-authorship network in ‘High Energy Physics (Theory)’ section (from 1991 to 2003) of arXiv (http://​arXiv.​org). The nodes in NetHEPT denote the authors, and the edges represent the co-authorship. HetHEPT has 15,229 nodes and 31,376 edges. (2) NetEmail: taken from the email interchange network in University of Rovira i Virgili (Tarragona). The nodes in NetEmail denote the members in the university, and the edges represent email interchanges among the members (the data set is available at http://​deim.​urv.​cat/​~alephsys/​data.​php). NetEmail has 1,133 nodes and 10,902 edges. (3) NetCLUB: taken from the relationship network in Zachary’s Karate club network, which is described by Wayne Zachary in [49]. NetCLUB has 34 nodes and 78 edges.

In this study, we assume that the influential degree from nodes i to j depends on the closeness of their relationship and the probability p(i) for node i where p(i), as defined in Problem description’ section, is the probability that node i would produce an influence propagation or would share knowledge with others. We apply the method proposed in [14] to estimate the closeness c(i,j) between i and j. Let degin(j) denote the in-degree of node j, then c(i,j)=e(i,j)/ degin(j), where e(i,j) denotes the number of edges from i to j. Due to the lack of ground truth, we independently assign uniform random 0.1%, 1%, and 10% to sharing probabilities p(i) for all the nodes i. Then we assume ∀(i,j)∈E, i has a chance of w ( i , j ) = p ( i ) e ( i , j ) deg in ( j ) to influence j.

We first evaluate the performance of our algorithms on NetCLUB. In algorithm SAMK CP or MAMK CP, σ(·) is computed by running MC simulation 1,000 times and get the average. Although AM2CP is not an optimal solution in the IC model, we still apply it in the splits in the simulation of IC model to improve the computational efficiency. Since MODUA is not flexible for the number of communities, we first apply MODUA to get a partition of NetCLUB and then apply our algorithms and SPECA to partition NetCLUB into the same number of communities. Figures 4 and 5 show the experimental results for the LT and IC models respectively. NetCLUB is partitioned into four communities. In terms of influence propagation, both SAMK CP and MAMK CP are better than MODUA and SPECA. SAMK CP outperforms MODUA and SPECA by about 40% and 70% respectively. In addition, from Figures 4 and 5, we can see the influence propagation of each partition is increasing gradually and linearly when the times of simulation increase, which reflects the reliability of experimental results.

In the second experiment, we compare MAMK CP with MODUA and SPECA on NetEmail. SAMK CP is removed due to its high computational complexity. Figures 6 and 7 show the experimental results. The network is partitioned into 88 communities. MAMK CP has the maximum sum of influence propagation. The performance of SPECA is poor compared with MAMK CP and MODUA. The influence propagation within the partition of SPECA is about two times less than that of MAMK CP and about one time less than that of MODUA.

In the last experiment, we compare MAMK CP with MODUA and SPECA on NetHEPT. Since this network has 15,229 nodes and 31,376 edges, we use the simplified version of MAMK CP. Figures 8 and 9 show the experimental results. The network is partitioned into 1,820 communities. MAMK CP is still better than MODUA and SPECA, but the gap between MAMK CP and MODUA in this experiment is less than that in the second experiment. This agrees with our intuition in that simplified MAMK CP has a lower computational complexity but also has some loss in performance. According to the three experimental results, we can conclude that the proposed algorithms are better than modularity-based and spectrum-based methods for finding communities in terms of influence propagation.