Social community evolution by combining gravitational relationship with community structure

Abstract

The analysis of communities and their evolutionary behaviors in dynamic social networks is a challenging topic. Although a lot of work on this topic is emerging, there are few methods which can reveal and track meaningful communities over time efficiently. In this paper, an approach of social community evolution based on gravitational relationship and community structure in a dynamic social network is proposed. Our proposed method that concentrates on both community structure and micro-blog content can be used to reveal and track the process of community evolution. First, we set up the undirected dynamic network in the original snapshot. Second, communities are initialized by constructing the basic nodes, and the other nodes can be iteratively searched and divided into corresponding communities. Third, we analyze community evolution and propose DCVIE algorithm to extract community evolution behavior. Finally, The experimental results show that the proposed method performs well on detecting communities as well as tracking communities evolution in dynamic social networks.

Keywords

Community detection community evolution gravitational relationship community structure

1. Introduction

Nowadays, Social media is still so popular because of its unprecedented convenience to permit human interaction with each other. With widely-available large-scale networks in social media, social activities of people are variable with the habits and hobbies that are slowly changing. This gives arise to the evolution of social network, such as there always exist many new registered users and disappearing users. Kumar et al. [18] exposed a surprising segmentation of these networks to simulate the evolution of social network. Our fundamental task is to study dynamic properties of social networks. The existing dynamic social network research mainly has two aspects from the perspective of analyzing object. One is studying of the type of users in social network [1, 18, 21] and the other is studying of the change of users and relations between users in social network [13, 14]. In the former one, users in social network are classified into three groups: passive, linkers and inviters. In the latter one, there are four adjusting policies specific to the four dynamic events: node adding, node deleting, link adding, link deleting.

Comparing with the existing methods, we have considered the evolution of users’ interest in a community. For example, there is a community $c_{t}$ whose members are interested in Iphone6s at the time $t$ . At the time $t+1$ , although the community has the same members and relationships, the community has evolved. Because members’ interests turn into IPhone7. This is very common in social networks.

In this paper, we analyze the community evolution through the gravitational relationship and community structure. Inspiring by the dynamic community evolution algorithm (GCEA) [5] that based on gravitational relationship refactoring, we refactor the gravitational relationship by considering the community structure and the interest cohesion. Our method can analyze the community evolution from two aspects: the visible community evolution and the invisible community evolution. The visible community evolution contains four dynamic events: node adding, node deleting, link adding, link deleting, and the invisible community evolution is the changing of the users’ interest.

The community evolution scenarios raise new challenges to traditional community detection algorithms. To deal with the visible community evolution and the invisible community evolution, a higher rationality and a dynamic adaptability are necessary and challenging. Therefore, we propose the DCVIE (the dynamic community visible and invisible evolution algorithm) to analyze the evolution of community. Our main contributions in this paper can be summarized as follows:

1.
The social network in the original snapshot is described as a tuple ( $\textit{SN}^{0}=\langle U^{0},R^{0}\rangle$ ). We let users be nodes and their relationships be edges. Then, we calculate the gravity between them by their attribute set.
2.
Communities are initialized by constructing the basic nodes. The other nodes can be iteratively searched and divided into corresponding communities.
3.
We analyze the community evolution and propose the DCVIE algorithm to track the visible and invisible evolution of the community.
4.
We analyze the performance of our method via experiments based on two datasets.

The rest of this paper is organized as follows. In Section 2, we survey the related work. We introduce the dynamic social network and its gravitational relationship in Section 3. In Section 4, we propose the approach, including a community detection algorithm, a dynamic community evolution algorithm and an algorithm for extracting community evolution behavior (DCVIE). We report the experimental results in Section 5. Finally, Section 6 concludes this paper and gives a brief account of future work.
2. Related work

Evolution of a particular social community can be represented as a sequence of events following each other in the successive timeframes within the temporal social network. In other words, the evolution is described by identifying group transformations from time $t$ to $t+1$ . So far, the method of detecting the dynamic communities can be classified into four categories: dynamic clustering, objective function optimization, representative node (community) detection, dynamic probability modeling [27, 28]. We can see from Table 1.

Table 1
Four categories of community evolution algorithms

Categories	Sources	Idea
The dynamic clustering	Chakrabarti et al. [3]	These methods see the time snapshot as clustering sample unit,
methods	Chi et al. [24]	integrate modeling the node distribution in time snapshot $t$ and $t-1$ .
	Kim and Han [10]
	Gao et al. [20]
The objective function	Blondel et al. [19]	These methods are guided by the optimization of community density
optimization methods	Nguyen et al. [13, 14]	function or modularity to estimate the community evolution by the
	Guo et al. [2]	structure changes.
	Zhou et al. [23]
The representative node	Zhang et al. [30]	These methods facilitated the adjusting process via tracing the
detection methods	Chen et al. [31]	representative nodes or communities.
	Takaffoli et al. [11]
	Ma and Huang [6]
The dynamic probability	Sarkar and Moore [16]	These methods assume the community distributions in each time
modeling methods	Sun et al. [7]	snapshot as the samples of latent community distribution, and establish
	Xin et al. [22, 29]	the probability model to associate the samples with latent community.

First, for the dynamic clustering methods, these methods [10, 20, 24, 26] are mainly based on the EC (Evolutionary Clustering) proposed by Chakrabarti et al. [3], seeing the time snapshot as clustering sample unit, integrated modeling the node distribution in time snapshot $t$ and $t-1$ . Chi et al. [24] proposed the Preserving Cluster Quality which emphasis on the cluster density and Preserving Cluster Membership methods which emphasis on the node similarity in the same cluster based on Kim and Han [10] proposed the Particle and Density based Evolutionary Clustering to improve the FacetNet method which proposed by Lin et al. [26].

Second, for the objective function optimization methods, these methods are guided by the optimization of community density function or modularity to estimate the community evolution by the structure changes. Blondel et al. [19] combined regional optimizing with hierarchical clustering to apply the FN [9] to dynamic community detection. Nguyen et al. [13, 14] designed four adjusting policies specific to the four dynamic events (node adding, node deleting, link adding, and link deleting). They proposed the Adaptive Finding Overlapping Community [13] and Quick Community Adaption [14] methods, which improved the community density function and modularity respectively. Guo et al. [2] and Zhou et al. [23] proposed the Evolutionary Community Structure Discovery and the multi-objective optimization method for dynamic community detection, respectively. The former’s goal was weighted dynamic community detection, and the latter revised the community assignments of new or changed vertexes during network update.

Third, for the representative node detection methods, Zhang et al. [30] proposed the Bulk Synchronous Parallel (BSP) method, which established the similarity measurement using the number of common neighbors and their connections. Duan et al. [4] proposed the compactness model to evaluate the regional community tightness. Chen et al. [31] proposed the representative-based community evolution tracing method, which made an assessment of the detected communities to determine which was stable. Takaffoli et al. [11] provided an evolutionary analysis method to identify the nodes, which adopts the steady-state and impact models to recognize the stable and representative nodes. Ma and Huang [6] proposed the Community Update and Tracking (CUT) model, which detected the seed community (the clique community).

Forth, for dynamic probability modeling methods, Sarkar and Moore [16] adopted the kernel method to construct the probability relation between nodes, and then utilized the probability relation between nodes and communities in each time segment to construct the Bayesian model between the nodes and latent communities. Sun et al. [7] proposed the Dirichlet Process Mixture (DPM) model which sampled the nodes in each time segment. They constructed the Bayesian model between nodes in the adjacent time segment. Thus, the latent communities can be detected by the LDA method. Xin et al. [22, 29] proposed the ARTs models to adaptively adjust the community structure as the the communitiesâ€™ semantic cohesion changes.

The traditional community evolution methods as discussed above focus on the same point, that is community structure. Most of these methods follow the same framework. First, they detect community by a static community detection algorithm in each timestep. Then, optimal match between two consecutive timesteps is implemented to generate the evolution events. However, in many cases data is not expected to evolve dramatically. Thus it is time-consuming to separately consider the network data for each timestep. Moreover, it is very time-consuming to use static community detect algorithm to find community in each timestep. On the other hand, for social networks, we can analyze the network from content. Because the evolution of the community lies not only in its structure, but also in the nature of the community.

In this article, we use the principle of gravity in physics. First of all, we build the initial social network and use the gravity between users to detect community. Then, based on the evolving sub network, the community is evolved by reanalysis of its gravity. Finally, we will use algorithm DCVIE to track the evolution behavior of the community. In this article, we divide the community evolution behavior into visible and invisible evolution. The visible community evolution contains seven events, which are “Continue” event, “Shrinking” event, “Growing” event, “Splitting” event, “Merging” event, “Dissolve” event and “Form” event. For the “Continue” event, “Shrinking” event and “Growing” event, the changes of community are not large in the consecutive time. In these three visual evolution events, the community may have an invisible evolution event. And we will analyze the invisible evolution event by gravitational relationship.

3. Dynamic social network and its gravitational relationship

3.1 The dynamic social network

To be able to describe evolution of social communities, we need to introduce the general concept of static social network. For a static network, it consists of nodes and edges, where a node indicates an individual who participates in the network and an edge between two nodes explains a link existing. A dynamic network is composed of a series of continuous static networks. In this article, the social network in the original snapshot is described as a tuple ( $\textit{SN}^{0}=\langle U^{0},R^{0}\rangle$ ), where $U^{0}$ represents a set of users in the original snapshot, $R^{0}$ is a set of users’ relationships. $\textit{SN}^{0}$ belongs to the sequence of $\{\textit{SN}^{0},\textit{SN}^{1},\ldots,\textit{SN}^{t},\ldots\}$ . Next, we will discuss the gravitational relationships in dynamic social networks.

3.2 Gravitational relationship

In this paper, we analyze the evolution of the community through the gravitational relationship and community structure. Inspired by the dynamic community evolution algorithm (GCEA) [5] that based on gravitational relationship refactoring in dynamic networks, we refactor the gravitational relationship by considering the community structure and the interest cohesion. In the universe, large numbers of heavenly bodies form some stable structures called galaxies under the action of the gravity among them. In [5], Yin et al. tried to use the gravity to measure the close degree between any two nodes in the complex networks. They constructed a gravitational relationship matrix to detect the communities of a static network, and further divided the nodes into communities according to the close degree. In Physics, the formula of universal gravitation is as follow:

$\displaystyle F=G\frac{m_{i}m_{j}}{r^{2}_{ij}}$ (1)

Where $F$ is the gravity between two spheres, G is the gravitational constant. $m_{i}$ and $m_{j}$ indicate the mass of sphere i and j respectively. $r_{ij}$ is the distance between two spheres. Yin et al. [5] redefined some parameters of the above formula. $f_{ij}$ is the gravity between two nodes. In [5], they just compared the size of the gravity without calculating the value of G, so they set G to 1. $m_{i}$ is the mass of node i, and mass as an inherent attribute of a node should reflect the local influence of the node. Due to the degree of a node can partly reflect the local influence of the node, They used the size of degree to represent the mass of the node. If two nodes are connected, the $r$ is 1, otherwise there is no gravity between them. Hence the gravity formula in [5] is as follow:

$\displaystyle f_{ij}=m_{i}m_{j}a_{ij}$ (2)

If two nodes are connected, the $a_{ij}$ is 1, otherwise, the $a_{ij}$ is 0.

Inspired by the above formula, we refactor the gravitational relationship by considering the community structure and the interest cohesion. $r_{ij}$ in Eq. (1) is the distance between two spheres. $r_{ij}$ is calculated by the reciprocal of similarity. Thus, in order to better measure the gravity between two nodes, we let interest similarity to measure the distance of them. In a social network, we can obtain a significant amount of useful information, such as users’ posts, to calculate the interest similarity between two users.

In our method, $U^{t}=\{\vec{u^{t}_{1}},\vec{u^{t}_{2}},\ldots,\vec{u^{t}_{i}},\ldots\}$ represents a set of users at time t. Each user is represented by the interest feature vector $\vec{u^{t}_{i}}$ . If $\vec{u^{t}_{i}}$ follows $\vec{u^{t}_{j}}$ , there is an edge $e^{t}_{ij}$ $\in$ R between $\vec{u^{t}_{i}}$ and $\vec{u^{t}_{j}}$ . We define $w^{t}_{ij}$ as the interest similarity between two users $\vec{u^{t}_{i}}$ and $\vec{u^{t}_{j}}$ . To compute the $w^{t}_{ij}$ , we improve the Tanimoto coefficient. The improved Tanimoto coefficient formula is as follows:

$\displaystyle w^{t}_{ij}=\frac{{\vec{u^{t}_{i}}}^{\prime}\bullet{\vec{u^{t}_{j% }}}^{\prime}}{{\arrowvert{\vec{u^{t}_{i}}}^{\prime}\arrowvert}^{2}+{\arrowvert% {\vec{u^{t}_{j}}}^{\prime}\arrowvert}^{2}-{\vec{u^{t}_{i}}}^{\prime}\bullet{% \vec{u^{t}_{j}}}^{\prime}}.$ (3) $\displaystyle{\vec{u^{t}_{i}}}^{\prime}=\{{\vec{u^{t}_{i1}}}^{\prime},{\vec{u^% {t}_{i2}}}^{\prime},\ldots,{\vec{u^{t}_{ik}}}^{\prime}\}\quad k=1\ldots\textit% {Count}(\vec{u^{t}_{i}}\bar{U}\vec{u^{t}_{j}})$ (4) $\displaystyle{\vec{u^{t}_{ik}}}^{\prime}=\begin{cases}1,&\textrm{$\textit{if}% \ \ r_{k}\in\vec{u^{t}_{i}}$,}\\ 0,&\text{Otherwise.}\end{cases}\quad r_{k}\in\vec{u^{t}_{i}}\bar{U}\vec{u^{t}_% {j}}.$ (5)

Where the ${\vec{u^{t}_{i}}}^{\prime}$ is a dimension-oriented Boolean expression of $\vec{u^{t}_{i}}$ , which can be obtained by incorporating features and changing the type of features to Boolean. $\vec{u^{t}_{i}}\bar{U}\vec{u^{t}_{j}}$ represents a vector that contains all features belonging to the vector ${\vec{u^{t}_{i}}}$ and ${\vec{u^{t}_{j}}}$ . In the $\vec{u^{t}_{i}}\bar{U}\vec{u^{t}_{j}}$ , elements are not equal to each other. The $r_{k}$ is an element of the $\vec{u^{t}_{i}}\bar{U}\vec{u^{t}_{j}}$ . The function Count (Vector e) is used to calculate the count of the element in vector e. For example, according to two vectors $\vec{u^{t}_{i}}=$ (music, movie, food, travel) and $\vec{u^{t}_{j}}=$ (movie, travel, car, basketball), we can obtain $\vec{u^{t}_{i}}\bar{U}\vec{u^{t}_{j}}=$ (music, movie, food, travel, car, basketball). Then, we will obtain vectors ${\vec{u^{t}_{i}}}^{\prime}=$ (1,1,1,1,0,0) and ${\vec{u^{t}_{j}}}^{\prime}=$ (0,1,0,1,1,1) by Eqs (4) and (5).

In order to better measure the gravity between two nodes, we use interest similarity to measure the distance between them. The greater the interest similarity of the two nodes, the smaller the distance between them. Thus, we measure the relationship between distance and interest similarity by Eq. (6).

$\displaystyle r^{t}_{ij}=\begin{cases}$Not exist$,&\textrm{$\text{if}\ \ a^{t}% _{ij}=0$,}\\ \infty,&\textrm{$\text{if}\ \ a^{t}_{ij}=1\bigwedge w^{t}_{ij}=0$,}\\ {(w^{t}_{ij})}^{-1},&\textrm{Otherwise.}\end{cases}$ (6)

In this article, we set G to 1, because G is the gravitational constant. Due to the degree of a node can partly reflect the local influence of the node, Yin et al. [5] used the size of degree to represent the mass of the node. We use the idea in [5] to let $m^{t}_{i}$ be the degree of the node $u^{t}_{i}$ . According to the Eqs (1) and (6), we refactor the gravitational relationship by combining the community structure and the interest cohesion. The improved formula is as follows:

$\displaystyle f^{t}_{ij}=\begin{cases}0,&\textrm{$\text{if}\ \ a^{t}_{ij}=0% \bigvee w^{t}_{ij}=0$,}\\ m^{t}_{i}m^{t}_{j}{(w^{t}_{ij})}^{2},&\textrm{Otherwise.}\end{cases}$ (7)

Based on the above analysis, we can establish a weighted social network which takes the users as the nodes and the users’ relationships as the edge. The gravity between every two users in the social network can also be obtained.

4. Dynamic community evolution

In physics, two spheres attracts each other by gravity. A node with larger $m^{t}$ is related to many nodes, that is, the node is important for social networks. In this chapter, we use these nodes with larger $m^{t}$ as the basic nodes (Bnodes). Let the Bnodes attract other nodes for community detection and community evolution analysis. We first propose community detection method, then analyze community evolution, and finally extract community evolution behavior. The flow chart of the method we proposed shows on Fig. 1. First, we use Algorithm 1 to detect the community at time t $.$ Then, we detect the community in the subsequent timestamps according to Algorithm 2. Finally, we get the community evolution behavior based on Algorithm 3.

Figure 1.

The flow chart of the method we proposed.

Definition 1: The Change Function $\Delta\{x^{t},x^{t+1}\}$ . $\Delta\{x^{t},x^{t+1}\}$ is the change of x in the two adjacent timestamps.

Definition 2: Community Evolution. Evolution of a social community can be described by identified community transformations from time $t$ to $t+1$ . If $\Delta\{U^{t},U^{t+1}\}>0$ $\bigvee$ $\Delta\{R^{t},R^{t+1}\}>0$ $\bigvee$ $\Delta\{f(c^{t}),f(c^{t+1})\}>0$ , then the social community evolves.

4.1 Community detection

Community detection aims at grouping nodes in accordance with the relationships among them to form strongly linked sub network from the entire social network. Different from the existing community detection algorithms, we use the Bnodes to attract other nodes to detect the community.

The greater the mass of a sphere, the more attractive it is in physics. Thus, we think of nodes with larger $m^{t}$ as the Bnodes, and use the Bnodes to attract other nodes. In this article, we choose the nodes whose degree is greater than its neighbor node as the Bnodes. The basic nodes is defined as: Bnode ${}_{i}=\{u_{i}|m_{i}\geqslant m_{j}\bigwedge a_{ij}=1\}$ . According to the gained Bnodes, we take these nodes as the initial communities, and then make these nodes attract other nodes. For any two nodes belong to the Bnodes, if they connect with each other, they can be divided into the same community. Otherwise, they will be divided into different communities.

After getting the initial community based on the Bnodes, we will detect community for other nodes by gravity. A node (not a basic node) would be drawn into a community directly if it only attracted by the community. However, if a node (not a basic node) is attracted by two or more communities simultaneously, it would belong to the community with the greatest attraction to it. Here, we define gravity of a node and a community as the average value of gravity between the node and other nodes in the community.

$\displaystyle f(u^{t}_{i},c^{t})=\frac{\sum_{j}m^{t}_{i}m^{t}_{j}{w^{t}_{ij}}^% {2}}{\sum_{j}{a_{ij}}}\ \ u^{t}_{j}\in c^{t}\bigwedge u^{t}_{i}\notin c^{t}$ (8)

When we go through all nodes which not belong to the Bnodes, we get the communities of the social network. The method of community detection as shown in Algorithm 4.1. At step 1, we find all the basic nodes in the social network. At steps 2–8, the nodes that belong to Bnodes will be partitioned into the corresponding community. At steps 3–4, if the two basic nodes are connected, we put them in the same community. At steps 5–6, if a basic node is not connected to other basic nodes, we create a community for it. At steps 9–10, for nodes that do not belong to Bnodes, they belong to the community with the greatest gravity.

UTF8gkai Community detection[1] $\textit{SN}^{t}$ $\textit{SN}^{t}=\{c^{t}_{1},c^{t}_{2},\ldots,c^{t}_{k}\}$ find Bnodes $u^{t}_{i}\in\textit{Bnodes}$ $u^{t}_{j}\in\textit{Bnodes}$ and $a_{ij}=1$ create a community for $u^{t}_{i}$ and $u^{t}_{j}$ create a community for $u^{t}_{i}$ $u^{t}_{i}\notin\textit{Bnodes}$ $u^{t}_{i}$ belongs to the $c^{t}_{k}$ that has a maximal value of $f(u^{t}_{i},c^{t}_{k}$ ) Eq. (8)

4.2 Community evolution

Evolution of a social community can be described by identified community transformations from time $t$ to $t+1$ . There are several approaches [5, 8, 15, 25] to definition of possible events in the community evolution. The short description of the most common changes can be found below.

1.
Continue. Continuation happens when two communities in the consecutive time are so much similar that it is hard to see any significant differences.
2.
Shrinking. The community shrinks when some nodes have left the community, making its size smaller than in the previous time snapshot.
3.
Growing. The community grows when some new nodes have joined the community, making its size bigger than in the previous time snapshot.
4.
Splitting. The community splits into two or more communities in the next time snapshot when few communities from time $t+1$ consist of nodes of one community from time t.
5.
Merging. The community has been created by merging several other communities, when one community from time $t+1$ consist of two or more communities from the previous time $t$ .
6.
Dissolve. It happens when a community ends its life and does not occur in the next time snapshot at all.
7.
Form. A new community occurs when a community which has not existed in the previous time snapshot t comes into existence in the next time snapshot $t+1$ .

Definition 3: Community Evolution Behavior. Community specific evolution process is called community evolution behavior. The community evolution behavior includes visible and invisible evolution. The visible community evolution contains seven events, which are “Continue” event, “Shrinking” event, “Growing” event, “Splitting” event, “Merging” event, “Dissolve” event and “Form” event.

In a dynamic network, the reason for the occurrence of events mentioned above is that nodes and edges change over time. Next, we first analyze the evolution of the community, and then track the evolution of the community behavior. In general, a social network $\textit{SN}^{t}$ to $\textit{SN}^{t+1}$ in the consecutive time may increase the nodes ( $\textit{nodes}^{+}$ ), reduce the nodes ( $\textit{nodes}^{-}$ ), increase the edges ( $\textit{edges}^{+}$ ) and reduce the edges ( $\textit{edges}^{-}$ ). In order to analyze the evolution of the community, we analyze the changes of nodes and edges. In Algorithm 4.2, $\Delta U_{t\rightarrow t+1}$ contains the changed nodes and its’ neighbor nodes in the consecutive time. If nodes (not basic nodes) leave, we update the gravity of the affected nodes and redistribute its communities (At steps 2–3). However, if nodes that belong to the Bnodes leave, we need to update the Bnodes and the gravity of the affected nodes and redistribute these nodes to the community (At steps 4–5). In the case of node increase and edge change, we first update the Bnodes and the gravity of the affected nodes (At step 9). Next, if Bnodes change, we analyze community evolution by following the Algorithm 4.1 (At steps 10–11). Otherwise, we redistribute the affected nodes to the community (At step 13). In step 13, we divide the affected nodes into the community with the greatest gravity.

UTF8gkai Dynamic community evolution[1] $\textit{SN}^{t}=\{c^{t}_{1},c^{t}_{2},\ldots,c^{t}_{k}\}$ , $\textit{SN}^{t+1}$ $\textit{SN}^{t+1}=\{c^{t+1}_{1},c^{t+1}_{2},\ldots,c^{t+1}_{k}\}$ $\textit{nodes}^{-}$ $\textit{nodes}^{-}\in\textit{Bnodes}$ Update the gravity of $\Delta U_{t\rightarrow t+1}$ and Bnodes, and redistribute the $\Delta U_{t\rightarrow t+1}$ Update the gravity of $\Delta U_{t\rightarrow t+1}$ , and redistribute the $\Delta U_{t\rightarrow t+1}$ $\textit{nodes}^{+}$ or $\textit{edges}^{+}$ or $\textit{edges}^{-}$ Update the gravity of $\Delta U_{t\rightarrow t+1}$ and BnodesBnodes change Algorithm 4.1redistribute the $\Delta U_{t\rightarrow t+1}$

After analyzing the evolution of the community, we will use algorithm DCVIE to track the evolution behavior of the community. In this article, we divide the community evolution behavior into visible and invisible evolution. The visible evolution of community contains seven events mentioned above, which are “Continue” event, “Shrinkin” event, “Growing” event, “Splitting” event, “Merging” event, “Dissolve” event and “Form” event. For the “Continue” event, “Shrinking” event and “Growing” event, the changes of community are not large in the consecutive time. Thus, we will analyze the invisible evolution of community. Because of the changes of nodes and edges, as well as the user’ interest changes in the consecutive time, the gravity of nodes in the community will change. Thus, we consider the average gravity change in the community as the invisible evolution of the community. The formula for average gravity change is shown in Eq. (10).

$\displaystyle f(c^{t}_{i})=\sum m^{t}_{j}m^{t}_{k}{w^{t}_{jk}}^{2}\ \ u^{t}_{j% }\in c^{t}_{i}\bigwedge u^{t}_{k}\in c^{t}_{i}\bigwedge j\neq k$ (9) $\displaystyle\Delta f(c^{t}_{i},c^{t+1}_{j})=\left|\frac{f(c^{t}_{i})}{\sum a^% {t}_{mn}}-\frac{f(c^{t+1}_{j})}{\sum a^{t+1}_{xy}}\right|\ \ u^{t}_{m},u^{t}_{% n}\in c^{t}_{i}\bigwedge u^{t+1}_{x},u^{t+1}_{y}\in c^{t+1}_{j}$ (10)

$f(c^{t}_{i})$ represents the gravity within the community $c^{t}_{i}$ , $\Delta f(c^{t}_{i},c^{t+1}_{j})$ represents the average gravity change of the two communities in the consecutive time. The total number of edges in community $c^{t}_{i}$ is represented by $\sum a^{t}_{mn}$ .

In order to track the evolution of the community, we define a community relationship map between two adjacent time snapshots according to the partial evolutionary graph proposed by [25]. First, we show the changes of social network through the ownership relationship between the community and the users. We only study the users belonging to $\Delta U_{t\rightarrow t+1}$ to improve the efficiency. For other communities that have not changed, we only analyze its invisible evolution. The ownership relationship between the communities and the users shows in Fig. 2. The relationship between the left part and the middle part of Fig. 2 shows the relationship between the users and the communities at t time. Similarly, the relationship between the right part and the middle part of Fig. 2 indicates the relationship between the users and the communities in $t+1$ time. According to Fig. 2, we can get the relationship between the communities from time t and the communities from time $t+1$ . By simplifying the Fig. 2, we define the community relationship map to directly show the relationship between the communities in two adjacent time snapshots. As shown in Fig. 3, the left part represents the communities at the time of t, and the right part represents the communities of the time $t+1$ . If the two communities have common nodes, there is an edge between the two communities. The weights on the edge indicates the probability that a community will be transformed into another. We use $(P(c^{t}_{1}\rightarrow c^{t+1}_{1}),P(c^{t+1}_{1}\rightarrow c^{t}_{1}))$ to represent the probability from the community $c^{t}_{1}$ to $c^{t+1}_{1}$ and the probability of $c^{t+1}_{1}$ to $c^{t}_{1}$ .

Figure 2.
The ownership relationship between the communities and the users.

Figure 3.
The community relationship map between two adjacent time snapshots.

Table 2
The condition of community evolution behavior

Evolution Type of Condition of evolution behavior Reason number Possible causes

behavior evolution of evolution

Continue Visible $\min\{P(c^{t}_{i}\rightarrow c^{t+1}_{j}),P(c^{t+1}_{j}\rightarrow c^{t}_{i})% \}\geqslant\kappa$ R1

Invisible $\min\{P(c^{t}_{i}\rightarrow c^{t+1}_{j}),P(c^{t+1}_{j}\rightarrow c^{t}_{i})% \}\geqslant\kappa$

$\bigwedge\Delta f(c^{t}_{i},c^{t+1}_{j})>\lambda$ R2

Shrinking Visible $1\geqslant P(c^{t+1}_{j}\rightarrow c^{t}_{i}>P(c^{t}_{i}\rightarrow c^{t+1}_{% j}))\geqslant\kappa$ R3 $\textit{nodes}^{-};\textit{edges}^{-}$

Invisible $1\geqslant P(c^{t+1}_{j}\rightarrow c^{t}_{i}>P(c^{t}_{i}\rightarrow c^{t+1}_{% j}))\geqslant\kappa$ R4

$\bigwedge\Delta f(c^{t}_{i},c^{t+1}_{j})>\lambda$

Growing Visible $1\geqslant P(c^{t}_{i}\rightarrow c^{t+1}_{j})>P(c^{t+1}_{j}\rightarrow c^{t}_% {i})\geqslant\kappa$ R5 $nodes^{+};edges^{+}$

Invisible $1\geqslant P(c^{t}_{i}\rightarrow c^{t+1}_{j})>P(c^{t+1}_{j}\rightarrow c^{t}_% {i})\geqslant\kappa$ R6

$\bigwedge\Delta f(c^{t}_{i},c^{t+1}_{j})>\lambda$

Spliting Visible/Invisible $\exists c^{t+1}_{i},c^{t+1}_{j},c^{t+1}_{k},\ldots\textit{satisfy}$ R7 $\textit{nodes}^{-};\textit{nodes}^{+};$

$P(c^{t+1}_{i}\rightarrow c^{t}_{l})\geqslant\kappa\bigwedge P(c^{t+1}_{j}% \rightarrow c^{t}_{l})\geqslant\kappa\bigwedge$ $\textit{edges}^{-};\textit{edges}^{+}$

$P(c^{t+1}_{k}\rightarrow c^{t}_{l})\geqslant\kappa\bigwedge\ldots$

$\bigwedge P(c^{t}_{l}\rightarrow c^{t+1}_{i}\bigcup c^{t+1}_{j}\bigcup c^{t+1}% _{k}\bigcup\ldots)\geqslant\kappa$

Merging Visible/Invisible $\exists\ c^{t}_{i},c^{t}_{j},c^{t}_{k},\ldots\ \textit{satisfy}$ R8 $\textit{nodes}^{-};\textit{nodes}^{+};$

$P(c^{t}_{i}\rightarrow c^{t+1}_{l})\geqslant\kappa\bigwedge P(c^{t}_{j}% \rightarrow c^{t+1}_{l})\geqslant\kappa\bigwedge$ $\textit{edges}^{-};\textit{edges}^{+}$

$P(c^{t}_{k}\rightarrow c^{t+1}_{l})\geqslant\kappa\bigwedge\ldots$

$\bigwedge P(c^{t+1}_{l}\rightarrow c^{t}_{i}\bigcup c^{t}_{j}\bigcup c^{t}_{k}% \bigcup\ldots)\geqslant\kappa$

Dissolve Visible/Invisible $\max\{P(c^{t}_{i}\rightarrow c^{t+1}_{j}),P(c^{t+1}_{j}\rightarrow c^{t}_{i})% \}<\kappa$ R9 $\textit{nodes}^{-};edges^{-}$

$\textit{at time}t$

Form Visible/Invisible $\max\{P(c^{t}_{i}\rightarrow c^{t+1}_{j}),P(c^{t+1}_{j}\rightarrow c^{t}_{i})% \}<\kappa$ R10 $\textit{nodes}^{-};\textit{edges}^{-}$

$\text{at time}\ t+1$

Reason number Theory for each mode

R1 The probability of transformation between two communities is greater than threshold $\kappa$ .

R2 Based on R1, the average gravity change of two communities is greater than threshold $\lambda$ in two adjacent timestamps.

R3 Based on R1, the probability of converting from a community at $t+1$ to a community at time $t$ is greater than the probability of going from $t$ to $t+1$ .

R4 Based on R3, the average gravity change of two communities is greater than threshold $\lambda$ in two adjacent timestamps.

R5 Based on R1, the probability of converting from a community at $t$ to a community at time $t+1$ is greater than the probability of going from $t+1$ to $t$ .

R6 Based on R5, the average gravity change of two communities is greater than threshold $\lambda$ in two adjacent timestamps.

R7 There are a number of communities at $t+1$ . The probability of converting each community into community C (at $t$ moment) is greater than threshold $\kappa$ . And the probability of community C converting to these communities is greater than threshold $\kappa$ .

R8 There are a number of communities at $t$ . The probability of converting each community into community C (at $t+1$ moment) is greater than threshold $\kappa$ . And the probability of community C converting to these communities is greater than threshold $\kappa$ .

R9 At time t, the probability of the transformation for two communities belonging to two timestamps is less than the threshold $\kappa$ .

R10 At time $t+1$ , the probability of the transformation for two communities belonging to two timestamps is less than the threshold $\kappa$ .

Table 2 shows the evolution of the community. Parameters $\kappa$ and $\lambda$ are thresholds. A continue event indicates that the users of a community remain in two adjacent time snapshots. The community exists as long as the gravity among its users are strong enough. When some users leave a community, this community will shrink. However, when a community absorbs new users, this community grows in its events. When the community remain in two adjacent time snapshots, if the average gravity of the community is greatly enhanced or weakened, it shows that the community has invisible evolution behavior. A split event implies that some users in a community stop to interact with each other in a particular period of time, causing the original community to split into two smaller communities. In a split event, the gravity of the original community is greatly weakened. Thus, there is an invisible evolution behavior in the split event. A merge event indicates that rich interactions have been created between users which previously were in different communities. Users in these communities eventually join as a new community. A merge event means that the gravity of the new community is greatly enhanced. A dissolve event implies the disappearance of gravity among users of a community in a particular period of time, which leads to the breakup of the community. A form event indicates that a new community is created because of the strengthening of gravity among users. The users in the new community were not in the same community in the previous time snapshot, but because of the increase of gravity, they create a new community. The algorithm of tracking the evolution of the community as shown in Algorithm 2. At step 1, the community relation map is built between time snapshots $t$ and $t+1$ . At steps 2–5, if the communities belonging to $\Delta c^{t,t+1}$ satisfy the conditions of evolution behavior in Table 2, we extract the corresponding evolution behavior of these communities. At steps 6–9, for communities not belonging to $\Delta c^{t,t+1}$ , if these communities have gravity changes that greater than the threshold $\lambda$ , we extract their invisible evolution behavior.

UTF8gkai DCVIE[1] $\textit{SN}^{t}=\{c^{t}_{1},c^{t}_{2},\ldots,c^{t}_{i}\}$ , $\textit{SN}^{t+1}=\{c^{t+1}_{1},c^{t+1}_{2},\ldots,c^{t+1}_{j}\}$ Evolution behavior of community Construct community relationship map $\Delta c^{t,t+1}$ between time snapshots $t$ and $t+1$ . $c^{t}_{i},c^{t+1}_{j}\in\Delta c^{t,t+1}$ Judge $c^{t}_{i},c^{t+1}_{j}$ meet the conditions of evolution behavior in Table 2. Output corresponding evolution behavior. $c^{t}_{i},c^{t+1}_{j}\notin\Delta c^{t,t+1}$ Judge $\Delta f(c^{t}_{i},c^{t+1}_{j})>\lambda$ . Output corresponding evolution behavior.
5. Experiments

Evolution	Type of	Condition of evolution behavior	Reason number	Possible causes
Continue	Visible	$\min\{P(c^{t}_{i}\rightarrow c^{t+1}_{j}),P(c^{t+1}_{j}\rightarrow c^{t}_{i})% \}\geqslant\kappa$	R1
	Invisible	$\min\{P(c^{t}_{i}\rightarrow c^{t+1}_{j}),P(c^{t+1}_{j}\rightarrow c^{t}_{i})% \}\geqslant\kappa$
		$\bigwedge\Delta f(c^{t}_{i},c^{t+1}_{j})>\lambda$	R2
Shrinking	Visible	$1\geqslant P(c^{t+1}_{j}\rightarrow c^{t}_{i}>P(c^{t}_{i}\rightarrow c^{t+1}_{% j}))\geqslant\kappa$	R3	$\textit{nodes}^{-};\textit{edges}^{-}$
	Invisible	$1\geqslant P(c^{t+1}_{j}\rightarrow c^{t}_{i}>P(c^{t}_{i}\rightarrow c^{t+1}_{% j}))\geqslant\kappa$	R4
		$\bigwedge\Delta f(c^{t}_{i},c^{t+1}_{j})>\lambda$
Growing	Visible	$1\geqslant P(c^{t}_{i}\rightarrow c^{t+1}_{j})>P(c^{t+1}_{j}\rightarrow c^{t}_% {i})\geqslant\kappa$	R5	$nodes^{+};edges^{+}$
	Invisible	$1\geqslant P(c^{t}_{i}\rightarrow c^{t+1}_{j})>P(c^{t+1}_{j}\rightarrow c^{t}_% {i})\geqslant\kappa$	R6
		$\bigwedge\Delta f(c^{t}_{i},c^{t+1}_{j})>\lambda$
Spliting	Visible/Invisible	$\exists c^{t+1}_{i},c^{t+1}_{j},c^{t+1}_{k},\ldots\textit{satisfy}$	R7	$\textit{nodes}^{-};\textit{nodes}^{+};$
		$P(c^{t+1}_{i}\rightarrow c^{t}_{l})\geqslant\kappa\bigwedge P(c^{t+1}_{j}% \rightarrow c^{t}_{l})\geqslant\kappa\bigwedge$		$\textit{edges}^{-};\textit{edges}^{+}$
		$P(c^{t+1}_{k}\rightarrow c^{t}_{l})\geqslant\kappa\bigwedge\ldots$
		$\bigwedge P(c^{t}_{l}\rightarrow c^{t+1}_{i}\bigcup c^{t+1}_{j}\bigcup c^{t+1}% _{k}\bigcup\ldots)\geqslant\kappa$
Merging	Visible/Invisible	$\exists\ c^{t}_{i},c^{t}_{j},c^{t}_{k},\ldots\ \textit{satisfy}$	R8	$\textit{nodes}^{-};\textit{nodes}^{+};$
		$P(c^{t}_{i}\rightarrow c^{t+1}_{l})\geqslant\kappa\bigwedge P(c^{t}_{j}% \rightarrow c^{t+1}_{l})\geqslant\kappa\bigwedge$		$\textit{edges}^{-};\textit{edges}^{+}$
		$P(c^{t}_{k}\rightarrow c^{t+1}_{l})\geqslant\kappa\bigwedge\ldots$
		$\bigwedge P(c^{t+1}_{l}\rightarrow c^{t}_{i}\bigcup c^{t}_{j}\bigcup c^{t}_{k}% \bigcup\ldots)\geqslant\kappa$
Dissolve	Visible/Invisible	$\max\{P(c^{t}_{i}\rightarrow c^{t+1}_{j}),P(c^{t+1}_{j}\rightarrow c^{t}_{i})% \}<\kappa$	R9	$\textit{nodes}^{-};edges^{-}$
		$\textit{at time}t$
Form	Visible/Invisible	$\max\{P(c^{t}_{i}\rightarrow c^{t+1}_{j}),P(c^{t+1}_{j}\rightarrow c^{t}_{i})% \}<\kappa$	R10	$\textit{nodes}^{-};\textit{edges}^{-}$
		$\text{at time}\ t+1$

Reason number	Theory for each mode
R1	The probability of transformation between two communities is greater than threshold $\kappa$ .
R2	Based on R1, the average gravity change of two communities is greater than threshold $\lambda$ in two adjacent timestamps.
R3	Based on R1, the probability of converting from a community at $t+1$ to a community at time $t$ is greater than the probability of going from $t$ to $t+1$ .
R4	Based on R3, the average gravity change of two communities is greater than threshold $\lambda$ in two adjacent timestamps.
R5	Based on R1, the probability of converting from a community at $t$ to a community at time $t+1$ is greater than the probability of going from $t+1$ to $t$ .
R6	Based on R5, the average gravity change of two communities is greater than threshold $\lambda$ in two adjacent timestamps.
R7	There are a number of communities at $t+1$ . The probability of converting each community into community C (at $t$ moment) is greater than threshold $\kappa$ . And the probability of community C converting to these communities is greater than threshold $\kappa$ .
R8	There are a number of communities at $t$ . The probability of converting each community into community C (at $t+1$ moment) is greater than threshold $\kappa$ . And the probability of community C converting to these communities is greater than threshold $\kappa$ .
R9	At time t, the probability of the transformation for two communities belonging to two timestamps is less than the threshold $\kappa$ .
R10	At time $t+1$ , the probability of the transformation for two communities belonging to two timestamps is less than the threshold $\kappa$ .

In this section, we use two dataset that are labeled Dataset1 and Dataset2 to study the performance of our method. The Dataset1 is obtained from Sina micro-blog platform by intelligent reptiles. We obtain the Dataset2 from the Micro-blog User Portrait Contest in 2016. The detailed information of the two datasets is shown in Table 3. Before reporting the experimental results, we first describe the methods comparison and the experimental setup.

Table 3
The two datasets for the experiments

	Dataset1
Snapshots	1	2	3	4	5	6
Users	780	780	768	764	762	789
Posts	704	664	555	507	730	811
Relationships	42369	42864	37415	39165	52900	58571
Snapshots	7	8	9	10	11	12
Users	774	778	782	782	776	795
Posts	596	565	690	785	955	1730
Relationships	56866	56349	57908	52842	38326	46630
	Dataset2
Snapshots	1	2	3	4	5	6
Users	1534	1546	1550	1550	1546	1546
Posts	6650	6329	7248	6264	6008	5136
Relationships	103712	117037	116897	121105	90135	97412
Snapshots	7	8	9	10	11	12
Users	1522	1514	1510	1590	1602	1593
Posts	4746	4756	4815	4511	5377	6320
Relationships	99087	101057	81462	109415	74455	86777

Figure 4.

The number of communities at different snapshots. ( $\textit{Num(C})$ represents the number of communities. We do not show the iLCD, because iLCD detects a large number of overlapping communities for each timestep and many of them are small.)

Figure 5.

The average community gravity of each snapshot via iLCD, LDM-CET, GCEA and our method.

Figure 6.

The average modularity of each snapshot via iLCD, LDM-CET, GCEA and our method.

All experiments are implemented in Python and performed on a PC with an Intel i7 4.0 GHz CPU and 8 GB memory. We conduct our experiments on two datasets and contrast the results with other proposed algorithms, such as the iLCD [17], LDM-CET [25] and GCEA [5]. The iLCD approach [17] updates the community structure at each timestep by analyzing the nodes and edges that have changed. It updates the communities mainly based on two metrics, i.e., the estimation of the mean number of second neighbors and the estimation of the mean number of robust second neighbors. The evolutionary behaviors of communities are obtained by matching the node-community memberships at two consecutive timesteps. The main idea behind LDM-CET [25] method is to detect dynamic communities by exploring the local views of nodes. Moreover, based on the dynamic communities that have been discovered, the global community structure can be derived by updating the historical community structure and the evolutionary behaviors of communities can also be tracked. Yin et al. [5] divide the evolutionary processes between adjacent snapshots into three phases and make use of the GCEA method to judge the evolutionary events of communities from the different variations of the core nodes chains, then adjust the communities via redistributing the core nodes chains of communities and refactor the gravitational relationship in the network. We first analyze the community quality of each timestamp from community gravity and community structure, and then analyze the accuracy, recall, and F values of each method to extract community evolution behavior.

Figure 7.

The F-score of the community evolution events tracked by different methods for Dataset1. (m1, m2, m3 and m4 represent our method, GCEA [5], LDM-CET [25] and iLCD [17], respectively.)

Figure 8.

The F-score of the community evolution events tracked by different methods for Dataset2. (m1, m2, m3 and m4 represent our method, GCEA [5], LDM-CET [25] and iLCD [17], respectively.)

Figure 9.

Visual and invisible evolution ratio in Continue, Shrinking and Growing events.

5.1 Evaluate of the community quality

Our method not only considers community structure, but detects communities by analyzing micro-blog content. Therefore, we will analyze the community quality from two aspects: the community gravity and community structure. The users in a common community have the highly similar interest in general. Thus, we contrast our method with other methods using an evaluating indicator, e.g., average community gravity. The average community gravity of a social network can be calculated by Eq. (11).

$\displaystyle\overline{f^{t}_{\textit{SN}}}=\frac{1}{n_{c}}\sum_{i}f(c^{t}_{i})$ (11)

Where $n_{c}$ means the number of communities in the social network at time $t$ . $f(c^{t}_{i})$ represents the sum of gravity in community $i$ at time $t$ , which shows in Eq. (9). In order to analyze the community quality from the community structure, we employ modularity $Q$ proposed by Newman and Girran [12]. The higher the value of modularity $Q$ , the stronger the community structure is. Therefore, we propose Eq. (12) to analyze the quality of community in the social network at time t based on modularity $Q$ .

$\displaystyle\overline{Q^{t}_{\textit{SN}}}=\frac{1}{n_{c}}Q^{t}=\frac{1}{n_{c% }}\sum_{i}(e_{ii}-{a_{i}}^{2})$ (12)

Where $\overline{Q^{t}_{SN}}$ represents the average modularity in the social network at time $t$ . $e_{ii}$ is the fraction of edges in community $i$ , and $a_{i}$ is the fraction of edges that connect two vertices in community $c_{i}$ .

Figure 4 shows the number of communities in the dynamic evolution of the two networks. we do not show the iLCD, because iLCD detects a large number of overlapping communities for each timestep and the number of them is large. Compared with our approach and LDM-CET, the number of communities by using GCEA is relatively stable. The number of communities is different in two adjacent timestamps, so the communities are evolving. We calculate the average community gravity and the average modularity of communities in different snapshots on the four methods, and the comparative result showed on Figs 5 and 6, respectively. The qualities of the obtained communities on the four methods all keep a high level. As shown in Fig. 5, our approach has a higher average community gravity in comparison with the other three methods. The GCEA method has a low average community gravity, which can be clearly seen in the Dataset2. The higher the average community gravity is, the higher the similarity between users in the community. The average community gravity in Dataset2 is higher than in Dataset1, because Dataset2 is pre-processed. From Fig. 6, we can see that the four methods have similar modularity values. Obviously, the modularity in the Dataset2 is higher than in the Dataset1. Compared with the other three methods, the modularity of the iLCD method is relatively low, which we can see in the Dataset1 and in the Dataset2.

5.2 Evaluate of extracting community evolution behavior

To evaluate different methods on tracking the evolutionary behaviors of communities, we extract the evolution behaviors according to the definitions in Table 2.

Table 4 shows the recall of the critical evolution events tracked by different methods. From the results, it can be observed that in most cases our method performs best, followed by GCEA. iLCD performs worst, because the number of communities detected by iLCD for each timestep is too large and many of them are small communities. The F-score values resulting from different methods are shown in Figs 7 and 8. It can be seen that our method and GCEA performs best on Dataset1, the differences are very slight. For the iLCD method, the F-score value in the Dataset2 is slightly higher than in the Dataset1. For our method, although F-score value in Dataset2 is slightly lower than that of Dataset1, our method still has higher F-score value compared to the other three methods. These results show that our method can lead to good results even if the network changes dramatically between two consecutive timesteps.

To study the evolution of users’ interest in the community, we discuss the invisible evolution of community in Continue, Shrinking and Growing events. As shown in Fig. 9, we can see that the community has an invisible evolution behavior at each timestep. At timestep 7–8, most communities have invisible evolution behavior. This shows that a lot of users’ interest has changed over this period of time. However, at timestep 9–10, only a small fraction of communities have invisible evolution behavior. This shows that only a few users have changed their interest over this period of time.

Table 4
The recall of the community evolution events tracked by different methods.

Timestep	Dataset1				Dataset2
	Our method	GCEA [5]	LDM-CET [25]	iLCD [17]	Our method	GCEA [5]	LDM-CET [25]	iLCD [17]
1–2	0.83	0.67	0.50	0.00	0.80	0.70	0.67	0.00
2–3	1.00	0.88	0.50	0.83	1.00	1.00	0.83	0.00
3–4	0.75	0.88	0.80	1.00	0.90	0.83	0.67	0.00
4–5	0.83	0.33	0.25	0.00	0.80	0.33	0.67	0.25
5–6	0.80	0.17	0.80	0.00	0.83	0.17	0.83	0.50
6–7	0.83	1.00	0.70	1.00	0.90	0.17	0.67	0.50
7–8	1.00	1.00	1.00	1.00	1.00	0.88	1.00	0.33
8–9	1.00	1.00	1.00	0.17	1.00	1.00	1.00	1.00
9–10	1.00	1.00	0.75	0.00	0.80	1.00	1.00	1.00
10–11	0.80	0.67	0.50	0.00	1.00	0.88	0.75	0.00
11–12	0.88	1.00	0.33	0.00	0.90	0.88	0.67	0.00

6. Conclusion and future work

In this paper, an approach of social community evolution based on gravitational relationship and community structure in a dynamic social network is proposed to deal with Micro-blog community evolution problem.

The innovation of this paper is that, we analyze community gravity relationship and community structure at each snapshot, and extract community evolution behavior between two snapshots. First, we describe the social network in the original snapshot as a tuple ( $\textit{SN}^{0}=\langle U^{0},R^{0}\rangle$ ). We let users be nodes and their relationships be edges, then calculate the gravity between them by the usersâ€™ attribute set. Second, we initialize communities by constructing the basic nodes, then iteratively search the other nodes and divide them into corresponding communities. Third, we analyze community evolution and propose DCVIE algorithm to extract community evolution behavior. Finally, we analyze the performance of our method via experiments.

In the future, it is interesting to study how to better analyze and utilize the impact of changes in users’ interest on the community.

Footnotes

Acknowledgments

This work is supported by the National Nature Science Foundation (Grant Nos 61472329 and 61532009), the grants from Scientific Research Fund of Sichuan Provincial Education Department (No. 17ZB0411) and the Innovation Fund of Postgraduate, Xihua University.

References

Cuzzocrea

Folino

and Pizzuti

, DynamicNet: an effective and efficient algorithm for supporting community evolution detection in time-evolving information networks, Proceedings of the 17th International Database Engineering and Applications Symposium, ACM, 2013, 148–153.

Guo

Wang

and Zhang

, Evolutionary community structure discovery in dynamic weighted networks, Physica A: Statistical Mechanics and its Applications 413 (2014), 565–576.

Chakrabarti

Kumar

and Tomkins

, Evolutionary clustering, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining (2006), 554–560.

Duan

et al., Community mining on dynamic weighted directed graphs, Proceedings of the 1st ACM international workshop on Complex networks meet information and knowledge management (2009), 11–18.

Yin

et al., An approach of community evolution based on gravitational relationship refactoring in dynamic networks, Physics Letters A 381.16 (2017), 1349–1355.

H.S.

and Huang

J.W.

, Cut: community update and tracking in dynamic social networks, Proceedings of the 7th Workshop on Social Network Mining and Analysis (2013), 6.

Sun

et al., Graphscope: parameter-free mining of large time-evolving graphs, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining (2007), 687–696.

Zhu

et al., A reconstructed event-based framework for analyzing community evolution, Big Data Analysis (2016), 1–4.

Girvan

and Newman

M.E.

, Community structure in social and biological networks, Proceedings of the national academy of sciences 99 (2002), 7821–7826.

10.

Kim

M.S.

and Han

, A particle-and-density based evolutionary clustering method for dynamic networks, Proceedings of the VLDB Endowment 2 (2009), 622–633.

11.

Takaffoli

et al., Tracking changes in dynamic information networks, Computational Aspects of Social Networks (CASoN), 2011 International Conference on (2011), 94–101.

12.

Newman

M.E.

and Girvan

, Finding and evaluating community structure in networks, Physical Review E 69 (2004), pp. 026113.

13.

Nguyen

N.P.

et al., Overlapping communities in dynamic networks: their detection and mobile applications, Proceedings of the 17th annual international conference on Mobile computing and networking, ACM, 2011.

14.

Nguyen

N.P.

et al., Adaptive algorithms for detecting community structure in dynamic social networks, INFOCOM, 2011 Proceedings IEEE, IEEE, 2011.

15.

İlhan

and Öğüdücü

S.G.

, Feature identification for predicting community evolution in dynamic social networks, Engineering Applications of Artificial Intelligence 55 (2016), 202–218.

16.

Sarkar

and Moore

A.W.

, Dynamic social network analysis using latent space models, ACM SIGKDD Explorations Newsletter 7 (2005), 31–40.

17.

Cazabet

and Amblard

, Simulate to detect: a multi-agent system for community detection, Web Intelligence and Intelligent Agent Technology 2 (2011), 402–408.

18.

Kumar

Novak

and Tomkins

, Structure and evolution of online social networks, Link mining: models, algorithms, and applications, Springer New York, 2010, 337–357.

19.

Blondel

V.D.

et al., Fast unfolding of communities in large networks, Journal of Statistical Mechanics: Theory and Experiment 2008 (2008), P10008.

20.

Gao

Luo

and Bu

, Evolutionary community discovery in dynamic networks based on leader nodes, 2016 International Conference on Big Data and Smart Computing (2016), 53–60.

21.

Zhong

et al., The evolution of communities in the international oil trade network, Physica A: Statistical Mechanics and its Applications 413 (2014), 42–52.

22.

Yang

and Xie

Z.Q.

, A semantic overlapping community detection algorithm based on field sampling, Expert Systems with Applications 42 (2015), 366–375.

23.

Zhou

et al., Multiobjective biogeography based optimization algorithm with decomposition for community detection in dynamic networks, Physica A: Statistical Mechanics and its Applications 436 (2015), 430–442.

24.

Chi

et al., Evolutionary spectral clustering by incorporating temporal smoothness, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining (2007), 153–162.

25.

Yang

and Lv

, A local dynamic method for tracking communities and their evolution in dynamic networks, Knowledge-Based Systems 110 (2016), 176–190.

26.

Lin

Y.R.

et al., Facetnet: a framework for analyzing communities and their evolutions in dynamic networks, Proceedings of the 17th international conference on World Wide Web 58 (2008), 685–694.

27.

Xin

Xie

Z.Q.

and Yang

, The adaptive dynamic community detection algorithm based on the non-homogeneous random walking, Physica A: Statistical Mechanics and its Applications 450 (2016), 241–252.

28.

Xin

Xie

Z.Q.

and Yang

, An adaptive random walk sampling method on dynamic community detection, Expert Systems With Applications 58 (2016), 10–19.

29.

Xin

et al., An overlapping semantic community detection algorithm base on the ARTs multiple sampling models, Expert Systems with Applications 42 (2015), 3420–3432.

30.

Zhang

et al., Parallel community detection on large networks with propinquity dynamics, Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining (2009), 997–1006.

31.

Chen

et al., Detecting and tracking community dynamics in evolutionary networks, 2010 IEEE International Conference on Data Mining Workshops (2010), 318–327.

Evolution	Type of	Condition of evolution behavior	Reason number	Possible causes
behavior	evolution			of evolution
Continue	Visible	$\min\{P(c^{t}_{i}\rightarrow c^{t+1}_{j}),P(c^{t+1}_{j}\rightarrow c^{t}_{i})% \}\geqslant\kappa$	R1
	Invisible	$\min\{P(c^{t}_{i}\rightarrow c^{t+1}_{j}),P(c^{t+1}_{j}\rightarrow c^{t}_{i})% \}\geqslant\kappa$
		$\bigwedge\Delta f(c^{t}_{i},c^{t+1}_{j})>\lambda$	R2
Shrinking	Visible	$1\geqslant P(c^{t+1}_{j}\rightarrow c^{t}_{i}>P(c^{t}_{i}\rightarrow c^{t+1}_{% j}))\geqslant\kappa$	R3	$\textit{nodes}^{-};\textit{edges}^{-}$
	Invisible	$1\geqslant P(c^{t+1}_{j}\rightarrow c^{t}_{i}>P(c^{t}_{i}\rightarrow c^{t+1}_{% j}))\geqslant\kappa$	R4
		$\bigwedge\Delta f(c^{t}_{i},c^{t+1}_{j})>\lambda$
Growing	Visible	$1\geqslant P(c^{t}_{i}\rightarrow c^{t+1}_{j})>P(c^{t+1}_{j}\rightarrow c^{t}_% {i})\geqslant\kappa$	R5	$nodes^{+};edges^{+}$
	Invisible	$1\geqslant P(c^{t}_{i}\rightarrow c^{t+1}_{j})>P(c^{t+1}_{j}\rightarrow c^{t}_% {i})\geqslant\kappa$	R6
		$\bigwedge\Delta f(c^{t}_{i},c^{t+1}_{j})>\lambda$
Spliting	Visible/Invisible	$\exists c^{t+1}_{i},c^{t+1}_{j},c^{t+1}_{k},\ldots\textit{satisfy}$	R7	$\textit{nodes}^{-};\textit{nodes}^{+};$
		$P(c^{t+1}_{i}\rightarrow c^{t}_{l})\geqslant\kappa\bigwedge P(c^{t+1}_{j}% \rightarrow c^{t}_{l})\geqslant\kappa\bigwedge$		$\textit{edges}^{-};\textit{edges}^{+}$
		$P(c^{t+1}_{k}\rightarrow c^{t}_{l})\geqslant\kappa\bigwedge\ldots$
		$\bigwedge P(c^{t}_{l}\rightarrow c^{t+1}_{i}\bigcup c^{t+1}_{j}\bigcup c^{t+1}% _{k}\bigcup\ldots)\geqslant\kappa$
Merging	Visible/Invisible	$\exists\ c^{t}_{i},c^{t}_{j},c^{t}_{k},\ldots\ \textit{satisfy}$	R8	$\textit{nodes}^{-};\textit{nodes}^{+};$
		$P(c^{t}_{i}\rightarrow c^{t+1}_{l})\geqslant\kappa\bigwedge P(c^{t}_{j}% \rightarrow c^{t+1}_{l})\geqslant\kappa\bigwedge$		$\textit{edges}^{-};\textit{edges}^{+}$
		$P(c^{t}_{k}\rightarrow c^{t+1}_{l})\geqslant\kappa\bigwedge\ldots$
		$\bigwedge P(c^{t+1}_{l}\rightarrow c^{t}_{i}\bigcup c^{t}_{j}\bigcup c^{t}_{k}% \bigcup\ldots)\geqslant\kappa$
Dissolve	Visible/Invisible	$\max\{P(c^{t}_{i}\rightarrow c^{t+1}_{j}),P(c^{t+1}_{j}\rightarrow c^{t}_{i})% \}<\kappa$	R9	$\textit{nodes}^{-};edges^{-}$
		$\textit{at time}t$
Form	Visible/Invisible	$\max\{P(c^{t}_{i}\rightarrow c^{t+1}_{j}),P(c^{t+1}_{j}\rightarrow c^{t}_{i})% \}<\kappa$	R10	$\textit{nodes}^{-};\textit{edges}^{-}$
		$\text{at time}\ t+1$

Social community evolution by combining gravitational relationship with community structure

Abstract

Keywords

1. Introduction

Table 1 Four categories of community evolution algorithms

3.1 The dynamic social network

3.2 Gravitational relationship

Table 3 The two datasets for the experiments

Table 4 The recall of the community evolution events tracked by different methods.

Footnotes

Acknowledgments

References

Table 1
Four categories of community evolution algorithms

Table 3
The two datasets for the experiments

Table 4
The recall of the community evolution events tracked by different methods.