1 Introduction

One of the fundamental and most studied features in a social network is the detection of central nodes, which can usually be considered as the most important nodes [7, 8, 13]. Centrality is widely-used for measuring the relative importance of nodes within a graph and it has many applications: in social networks to determine the most influential or well-connected people; in the Web graph to rank pages in a search; in a terrorist network, to detect agents that are critical for facilitating the transmission of information; for the dissemination of information in P2P Networks, Decentralized Online Social Networks and Friend-to-Friend Networks [11].

There is a plethora of centrality definitions: degree centrality [18], closeness centrality [5], graph centrality [15], stress centrality [19], betweenness centrality [12], each one of them useful to detect specific properties and with significantly different computational costs. Here we consider four of them: the degree, closeness, betweenness, and PageRank-centrality.

Degree centrality, i.e. the degree \(d_{v}\) of a vertex v, is the simplest measure of centrality: it just takes into account how many direct, “one hop” connections each node has to other nodes of the network, hence it can be applied to detect popular individuals, agents who are likely to hold most information or individuals who can quickly connect with the wider network. The degree centrality of a node is very cheap to compute but, being a purely local notion, it is often unable to recognize the relevance of certain nodes. In this paper with the term degree we refer to in-degree centrality.

One of the most popular measures, even if computationally expensive for large graphs, is betweenness-centrality. It helps to detect nodes which act as “bridges” between other nodes in a network. It does this by computing the shortest path for each pairs of nodes and counting, for each node, the number of such paths which include it. Betweenness centrality is suitable for finding vertices who influence flows (such as information flow) in the network.

A third measure considered below is the closeness-centrality, which assigns to each node a score that is proportional to the reciprocal of the sum of all distances between the node and all other nodes. This definition of centrality is useful for quickly finding the agents who are in good position to influence the entire network. However, in a highly connected network most nodes often have a similar score.

Finally, PageRank-centrality was introduced in [9] and it recursively quantifies a “value’, the PageRank, of a node based on: (i) the number of links it receives, (ii) the link propensity of the linkers (that is, the number of outgoing links of each in-going node), and (iii) the centrality of the linkers, that is their PageRank.

To study how influential users evolve over the time, we analyze the distribution of the centrality measures on an temporal evolutionary model of the Twitter network, the Dynamic Retweet Graph (DRG) proposed in [3] and partially analyzed in [2, 4].

This model has two major features: (i) it is based on the retweet graph, since that allows to better represent relationships among users and the information flow in Twitter [16, 17] and, (ii) once a tweet has been retweeted for the last time all the edges representing retweets of this tweet are deleted, to model the loss of relevance of the tweet content.

The temporal model we consider coincides with other temporal models in the growing phase [6, 14], that is a new vertex is added when a new user first acts, either sending a tweet or retweeting an existing one, and a new directed edge \((a,b)\) is inserted when an user a retweets for the first time a tweet of b, if an edge already exists then a timestamp is added to it. Conversely, as the decreasing stage happens when a tweet is no more retweeted, all the vertices and the edges, not involved in other retweeting processes, are deleted at once. As shown in previous experimentations [2, 4], this evolutionary model better captures the information flow in Twitter. DRGs seem to better represent the double nature of the Twitter platform: social network and news media [16, 17].

For what concerns the use of centrality measures to assess influential or authoritative users, Kwak et al. [16] compared three measures of influence: in-degree centrality, PageRank centrality in the following/follower network and the number of retweets on Twitter. In Cha et al. [10] three different measures of influence are compared: in-degree centrality, the number of retweets and mentions on Twitter. The results indicate that users with high in-degree were not necessarily influential.

In this paper, we study the evolution of the most influential users in the microblogging social network platform Twitter with respect to four centrality measures (betweenness, degree, closeness, and PageRank) and we analyze their behavior on the DRG evolutionary model of the retweet social networks proposed in [3].

We consider two different kind of data sets, first introduced in [1] and updated and refined in [3]: the event driven retweet graphs based on the events Black Friday 2015 and the World Series 2015 and the Italian Sampling that is the firehose retweet graph, filtered by language (i.e. Italian) from the whole Twitter stream.

The four centrality measures are analyzed in three different frameworks: (i) with respect to the sequence of DRG temporal graphs; (ii) with respect to the static cumulative graph, that is the graph that contains all the nodes and edges and (iii) with respect to the kind of networks considered, that is event driven or the firehose.

We derive that the DRGs allow to detect the most authoritative users, since:

  1. 1.

    in all cases the closeness centrality provides too many central nodes, hence it is useless to detect influential users;

  2. 2.

    with regard the other measures, almost all nodes have null or very low centrality;

  3. 3.

    vertices with centrality values above \(75\%\) of the maximum is a small set and they are often repeated in the three centrality measures;

  4. 4.

    the above observations hold also for the static graphs (the cumulative DRG);

  5. 5.

    central nodes in the sequence of DRG temporal graphs have high centrality in static graphs.

2 DRG temporal graphs

In this paper we will use a definition of Dynamic Retweet Graph (DRG) slightly different from the one in [4].

A DRG graph \(G = (V,E, \ell )\) is defined as follows: nodes in V are Twitter accounts and a direct edge \(e\in E\) represents an interaction (a retweet) between two accounts. In particular, there is a directed edge from an account a towards an account b, if a has retweeted at least one tweet of b, that can be itself already a retweet. Observe that user a may retweet several tweets of b. Information on such retweets is provided, for each edge \(e=(a,b)\), by a list \(l(e)\) of pairs \((i, t)\) where i is the id of a tweet and t is the time when a retweeted i from b. Each list \(l(e)\) is ordered in non-decreasing order with respect to the timestamp t.

For each tweet i, we define the date of death of i (in short, \(\texttt {dod}(i)\)) as the timestamp of the last retweet of i, that is

$$\texttt{dod}(i) = \max_{e\in E} \{ t: (i,t) \in \ell(e) \}. $$

Consequently, we define the expiration date of an edge e (in short, \(\texttt {ed}(e)\)) as the timestamp from which all tweets associated to e will be dead. Formally,

$$\texttt{ed}(e) = \max\{ \texttt{dod}(i): (i,t) \in \ell(e) \}. $$

On the contrary, the creation date of an edge \(e=(a,b)\) (in short, \(\texttt {cd}(e)\)) is the timestamp b retweets a for the first time, formally:

$$\texttt{cd}(e) = \min\{ t: (i,t) \in \ell(e) \}. $$

We define a DRG temporal graph at time t the subgraph \(G_{t} = (V_{t}, E_{t})\) of the DRG G at time t as follows: \(E_{t}\) contains any edge e such that \(\texttt {cd}(e) \leq t \leq \texttt {ed}(e)\); \(V_{t}\) is the set of nodes induced by \(E_{t}\).

For example if G is the retweet graph represented in the left part of Fig. 1, \(G_{30}\) contains edges \((a,b)\) and \((c,a)\) and the induced vertices since \((c,b)\) expires at timestamp 25. For all \(20 \leq t \leq 25\), \(G_{t}\) contains all edges of G.

Fig. 1
figure 1

On the left side, an example of a DRG retweet graph. Edges are labeled by pairs with the id of the tweet and the timestamp of the retweet. The center table shows the date of death of all tweets in the graph. On the right side, for each edge of G is represented its creation and expiration date

Full size image

3 Data sets

For the experiments we use the dataset of [3] that consists in two different classes of retweet graphs: the event driven retweet graph, filtered by topics about specific events (i.e. the Black Friday 2015 and the World Series 2015) and the Italian Sampling retweet graph, filtered by the Italian language from the whole Twitter stream. To obtain the Italian Twitter Sampling we use a list of the most used Italian stop words and the Twitter native selection function for languages. In Table 1, we show the dimensions of the three graphs.

Table 1 Dimensions of the dataset
Full size table

In Fig. 2 we present the evolution of the dimensions of the three datasets over the period of observation. Note that the event-driven datasets (World Series and Black Friday) show a rapid growth close to the events, and then a slow decline. Differently, the Italian Sampling have a smooth and stable behavior, ignoring the border effects.

Fig. 2
figure 2

Number of vertices (blue) and number of edges (green) of: World Series, Black Friday, and Italian Sampling, as functions of hours

Full size image

4 Experimentation

For each graph G of our dataset, we consider the sequence of DRG temporal graphs \((G_{t_{i}} )_{i\geq 0}\) where \(t_{i + 1} - t_{i}\) is 4 hours. For each \(G_{t}\) we compute the four centrality values (betweenness, closeness, degree, and PageRank centrality) of each vertex of the graph.

Given the centrality measure c, the relative centrality value with respect to c of a vertex u is the ratio between \(c(u)\) and the maximum value of \(c(\cdot )\).

Preliminary considerations

Regarding the closeness centrality, we find that the relative centrality values are above 0.9 for almost one third of the nodes (see Fig. 3a). As a consequence the closeness centrality is quite useless to determine the more influential nodes in the graph.

Fig. 3
figure 3

a Trend over time of percentage of nodes with relative closeness centrality greater than 0.9. b The maximum relative degree, PageRank and betweenness centrality values of the 99.9-th percentile over time

Full size image

Conversely, the other centrality measures (degree, betweenness, and PageRank) reveal an opposite behavior: excluding the first and last timestamp, \(99.9\%\) of vertices always have centrality values below the \(20\%\) of the maximum. Figure 3b shows the evolution over time of the three centrality values below which the \(99.9\%\) of all values fall (99.9-th percentile). Observe that, from Fig. 3b it results that the highest values are at the very beginning of time sequences, when there is still much instability. After that, values fall below 0.05.

Analysis of temporal graphs

We say that a node is central (with respect to a centrality measure) if its centrality value is at least 75% of the maximum. From the previous observations it follows that if we restrict ourselves to the betweenness, degree and PageRank measures, the number central nodes is so small that we can study them one by one. Let G be a DRG, c be a centrality and t be a timestamp, we define \(A_{G, c, t}\) as the set of central node of \(G_{t}\) with respect to c. Table 2 shows the number of central nodes for each dataset and centrality measure.

Table 2 Number of nodes that have been central at least once for dataset and centrality measure
Full size table

In Fig. 4, are shown the sets \(A_{G,c,t}\) for the three datasets. The x-axis represent the time and in the y-axis are reported the vertex ids. In the same plot are collected the informations regards the three centrality measures each of which is represented by a color: green for the betweenness; red for the degree; and blue for the PageRank centrality. An horizontal segment in correspondence to node u that intersects timestamp t means that \(u \in A_{G,c,t}\) where c is the centrality measure associated to the segment color.

Fig. 4
figure 4

Temporal evolution of AG,c,t for the three datasets with respect to the betweenness (in green), degree (in red), and PageRank (in blue) centrality measure

Full size image

Nodes that are central for more than one centrality measure are grouped together in the lower portion of the plots. We have observed that there are nodes central only with respect the betweenness centrality measure and for a very short period. These nodes do not add any useful information therefore, in order to make the picture clearer, we have grouped together and represented them by a pseudo-node denoted as more. In the World Series the more node is the union of the segments corresponding to 6 nodes; in the Black Friday 29; and in the Italian Sampling 21. From the above analysis we get the following observations:

  • For all datasets, the degree centrality always produces a total number of central nodes lower than the other measures. Conversely, betweenness centrality is the one that produces more.

  • For all datasets and all the centrality measures, there are nodes that are central for long periods: this trend is more prominent for degree and PageRank centrality.

  • A significant overlap between the central vertices with respect the three measures. For example vertex 572 in Italian Sampling is central for most of the time also for all the three measures (see the third plot of Fig. 4).

Comparison with the static cumulative DRGs

The static cumulative DRG or cumulative DRG is obtained from the DRG ignoring the temporal data: it consists of a direct graph where the presence of edge \((a,b)\) means that user a has retweeted user b at least once.

This last analysis involves the centrality measures of the static cumulative DRGs G representing the three datasets. Similarly to DRGs temporal graphs, a large portion of vertices, varying form \(28\%\) (for World Series) to \(50\%\) (for Black Friday), have closeness centrality above \(90\%\) of the maximum, hence, we discard it.

On the contrary, for betweenness, degree, and PageRank centralities almost all the nodes have a value below \(1\%\) of the maximum. Table 3 shows, for each dataset and for each measure, the percentage of vertices whose relative centrality value is at most 0.01.

Table 3 Percentage of vertices in the cumulative DRGs whose relative centrality value is at most 0.01
Full size table

Our goal is to compare the centrality measures in the cumulative DRGs with the ones in the temporal DRGs. Given a dataset and a centrality measure c, for each node u, we have:

  • a single centrality value \(c(u)\), for the cumulative DRGs;

  • a sequence of centrality values \(c_{0}(u), c_{1}(u),\ldots \), for the temporal DRGs, one value for timestamp.

In order to make the two data sets comparable, we aggregate the sequence of centrality values \(c_{0}(u), c_{1}(u),\ldots \) into a single value \(s(u)\) given by the sum of all \(c_{i}(u)\). Finally, we can compare the sequence of centrality values of the cumulative DRGs with the sequence of the \(s(\cdot )\) values of the temporal DRGs. Table 4 shows the Pearson correlation coefficients between these observations. It turns out that there is a strong correlation in the case of degree and PageRank centralities. Instead, for betweenness centrality the correlation coefficient varies considerably.

Table 4 Pearson correlation between the centrality values in the cumulative DRGs and the aggregated centrality values in the temporal DRGs
Full size table

From an in-depth analysis we discover that also for the betweenness centrality there is a strong relationship between nodes that are central in both the cumulative DRGs and the temporal DRGs. Table 5 shows the relative betweenness centrality value in the Black Friday cumulative DRG of all central nodes in the Black Friday temporal DRGs with respect to the same centrality measure.

Table 5 Relative betweenness centrality in the cumulative Black Friday dataset of nodes that are central in the temporal graphs
Full size table

It is interesting to note that 31 of the 44 listed nodes belong to the \(0.03\%\) (=100 − 99.97, see Table 3) of vertices whose relative betweenness centrality is at least 0.01. That is a large majority of nodes that are central in temporal graphs are also central in the whole graph. Such behavior is even more pronounced in the World Series and Italian Sampling datasets. Table 6 and 7 show the analogue of Table 5 for the World Series and Italian Sampling datasets. In the World Series (resp. Italian Sampling) case there is only 1 out of 15 (resp. 4 out of 31) central nodes in the temporal graph with a relative centrality in the cumulative graph less than 0.01.

Table 6 Relative betweenness centrality in the cumulative World Series dataset of nodes that are central in the temporal graphs
Full size table
Table 7 Relative betweenness centrality in the cumulative Italian Sampling dataset of nodes that are central in the temporal graphs
Full size table

Finally, if we consider the degree and PageRank centrality measures the above described behavior is even more evident: all central nodes (except for node 3) in the temporal graphs belong to the ≈ 0.2% of nodes with relative centrality in the cumulative graph higher than 0.01. The three exceptions are related the PageRank measure for Black Friday (two nodes) and Italian Sampling (one node).

5 Discussion and conclusions

In this paper we have studied the evolution of four centrality measures (betweenness, degree, closeness, and PageRank) on the DRG temporal retweet graphs based on three datasets: Black Friday, World Series, and Italian Sampling. Our main results can be summarized as follows: (i) too many nodes are central with respect closeness centrality, hence this measure is useless to detect influential users; (ii) for the other measures, the number of nodes with very low centrality is very high and the sets of central nodes (with centrality values above \(75\%\) of the maximum) are very small and quite similar in the three measures; (iii) similar results hold also for the static cumulative graphs where the sets of nodes with relevant centrality contain central nodes in the sequence of DRG temporal graphs.

As pointed out in [4], the DRG temporal graphs derived from our datasets are quite sparse: this could explain the small number of central nodes respect to the three centrality measures.

According to the above analysis the approach based on the DRG temporal graph and the centrality measures represent a promising approach for detecting influencers in the microblogging Twitter platform. However, this method must be further refined in order to exclude from the influencer the nodes that are central for too little time.