Introduction

The betweenness centrality of a node in a network is defined as the fraction of the shortest paths between all the pairs of nodes that pass through it. Betweenness centrality is well suited for measuring the influence of a node over the information spread through the network [3,20], to identify boundary spanners (i.e., nodes acting as bridges between two or more subnetworks), and to measure the "stress" (in the sense of a higher usage) that a node must undergo during network activities [5,6,9,13]. Due to its relevance in network analysis, betweenness centrality has been largely investigated in the past, and several extensions, tailored to specific contexts, have been proposed (see, for instance, [26,10,11,4]). Also in the context of the Internet of Things (IoT), several approaches for the computation of betwenness centrality have been presented [15,23,17].

However, the classical betweenness centrality is not able to correctly evaluate the centrality of nodes in a multiple IoT scenario, i.e., a scenario where several networks of smart objects (SO) cooperate with each other. In such a scenario (known as Multi-IoT or MIoT in the literature [2,12,18,25]), IoT (i.e., networks of SO) are interconnected thanks to those nodes simultaneously belonging to two or more of them. We call cross nodes (c-nodes) these nodes and inner nodes (i-nodes) all the other ones. Then, a c-node connects at least two IoT of the MIoT and plays a key role in favoring the cooperation among i-nodes belonging to different IoT. As a consequence, the nodes of a MIoT are not all equal: cnodes will presumably play a more important role than i-nodes for supporting the activities in a MIoT. Here, the classical betwenness centrality is not able to distinguish c-nodes from i-nodes and to evidence the key role played by c-nodes in favoring communication and cooperation between SO belonging to different IoT of the MIoT.

In this paper, we aim at providing a contribution to address this problem. Indeed, we propose three new measures of betweenness centrality, well suited for a MIoT and, more in general, for a scenario consisting of a set of related IoT. These measures are called Inner Betweenness Centrality (IBC), Soft Cross Betweenness Centrality (SCBC) and Hard Cross Betweenness Centrality (HCBC). They have been designed to clearly distinguish the contributions of c-nodes and i-nodes and we show that they are able to reach this objective. In particular, IBC has been conceived for measuring the betweenness centrality with a focus on a single IoT of the MIoT and it privileges i-nodes over c-nodes. As will be clarified in the following, it does not coincide with the classical betweenness centrality because, differently from this last one, it also considers paths which connect two nodes of the same IoT but, at the same time, involve nodes belonging to other IoT of the MIoT. By contrast, SCBC and HCBC are specialized to measure the betweenness centrality of nodes by privileging paths involving more IoT of the MIoT and, therefore, c-nodes over i-nodes. As it is indicated by their names, this privilege is more marked in HCBC than in SCBC.

This paper is organized as follows. In Section 2, we provide an overview of related literature. In Section 3, we illustrate the MIoT paradigm in detail. In Section 4, we introduce our new betweenness centrality measures. In Section 5, we describe our experimental analysis. Finally, in Section 6, we draw our conclusions and have a look at some possible future developments of our research efforts.

Related Literature

As one of the most important centrality measure, betweenness centrality [13] has been the subject of in-depth studies in the literature [9,8]. Recognizing high spreading power nodes is fundamental in social networks but, based on its definition, the cost for computing the betweenness centrality of a node is high. For this reason, several heuristic approaches, aiming at providing the closest possible value of the betweenness centrality of a node in a reasonable time, have been proposed in the past (see [7,1,14,24], to cite a few).

As for the IoT, which is an example of a very dynamic and constantly evolving network, the approaches for the incremental computation of betweenness centrality are extremely interesting. Among these, we mention the ones described in [15,23,17]. Specifically, in [15], the authors propose iCENTRAL, which is well suited for large and evolving biconnected graphs. In [23], the authors illustrate an approach for a quick incremental computation of betweenness centrality. After a pre-processing phase, the computational cost of this approach is independent of the network size. In [17], the authors describe an approach that reduces the search space by finding a set of candidate nodes that are the only ones to be updated during the incremental computation of the betweenness centrality.

Surprisingly, despite the strong tie existing among betweenness centrality and information diffusion, there are very few studies concerning the role of betweenness centrality in IoT. To the best of our knowledge, the only approaches dealing with centrality in IoT have been proposed as part of methods for determining trustworthiness [22] or network navigability [19,21] in IoT. Anyway, in all these cases, centrality is simply a part of the proposed approaches and not the central topic to investigate. By contrast, betweenness centrality (or better, the redefinition of betweenness centrality in a MIoT scenario) is one of the main goals of this paper, and all the results we present here can be applied in many contexts comprising the two mentioned above, along with several other ones.

The MIoT paradigm

In this section, we provide a brief overview of the MIoT paradigm. In particular, we introduce those concepts necessary to understand the rest of the paper. The interested reader can find all details about this paradigm in [2,18,25].

A MIoT M can be defined as a set of m IoT:

M = {I 1 , I 2 , • • • , I m }

, where I k is an IoT. Consider an object o j of M. We assume that, if o j belongs to I k , it has an instance ι j k , representing it in I k .

In M, a set M D j of metadata are associated with o j . The MIoT paradigm considers a rich set of metadata for an object, because metadata play a key role in favoring the interoperability of IoT and of their objects, which is the ultimate objective of a MIoT. M D j consists of three different subsets:

M D j = M D D j , M D T j , M D O j .

Here, M D D j represents the set of descriptive metadata, which denote the type of o j . In order to represent and handle descriptive metadata, our paradigm uses a proper taxonomy, such as the one defined by the IPSO Alliance3 . M D T j represents the set of technical metadata. These are compliant with the object type. The IPSO Alliance provides a well defined set of technical metadata for each object type. Finally, M D O j represents the set of operational metadata. These regard the behavior of o j and is defined as the union of the sets of the operational metadata of the instances of o j .

It is possible to represent I k by means of a graph: G k = N k , E k where N k indicates the set of the nodes of I k . There is a node n j k for each instance ι j k of an object o j in I k . Instead, E k denotes the set of the edges of I k . There is an edge e jq k = (n j k , n q k ) if there exists a certain form of relationship (for instance, proximity) between the instances ι j k and ι q k of the objects o j and o q in the IoT I k .

Finally, a MIoT M can be modeled as a graph G = N, E were:

-N = m k=1 N k ; in other words, N is the union of the sets of the nodes of the corresponding IoT.

-E = E I ∪ E C . Here, E I = m k=1 E k . E C = {(n j k , n jq )|n j k ∈ N k , n jq ∈ N q , k

= q}; in this definition, n j k and n jq are the nodes corresponding to the instances ι j k and ι jq of o j in I k and I q . In other words, the set E of the edges of M consists of two subsets, E I and E C . E I is the set of the inner edges of M and is the union of the sets of the edges of the corresponding IoT. E C is the set of the cross edges of M; there is a cross edge for each pair of instances of the same object in different IoT.

We call: (i) i-edge an edge of M belonging to E I ; (ii) c-edge an edge of M belonging to E C ; (iii) c-node a node of M involved in at least one c-edge; (iv) i-node a node of M not involved in any c-edge; (v) c-object an object having at least one pair of instances whose corresponding nodes are linked by a c-edge.

Redefining Betweenness Centrality for a MIoT

Given a node n j of a graph G, the classic definition of betweenness centrality is the following:

BC(n j ) = ns∈N,nt∈N,ns =nj ,nt =nj σ nsnt (n j ) σ nsnt

where σ nsnt is the total number of the shortest paths from n s to n t , whereas σ nsnt (n j ) is the number of those shortest paths passing through n j .

If we apply BC to the graph G k associated with an IoT I k and consider I k isolated from the MIoT, this formula involves shortest paths which only pass from nodes of I k . In order to consider also the potential shortest paths that connect nodes of G k but pass through nodes of the other IoT of the MIoT, it should be applied to the graph G corresponding to the whole MIoT. However, in this way, it does not capture that a MIoT consists of different autonomous IoT cooperating with each other thanks to c-nodes, which play a key role that should be evidenced by any measure of centrality conceived for a MIoT. We argue that, owing to these weaknesses, BC could present several problems in a MIoT context, especially when it is necessary to compute a centrality measure, which privileges those nodes that allow the crossing from an IoT to another.

To address the challenges mentioned above, we define three new centrality metrics. The first of them is called Inner Betweenness Centrality (IBC) and is defined as follows.

Let n j k ∈ N k be the node corresponding to the instance ι j k of the object o j in the IoT I k of the MIoT M. The Inner Betweenness Centrality IBC(n j k ) is defined as:

IBC(n j k ) = ns k ∈N k ,nt k ∈N k ,ns k =nj k ,nt k =nj k σ ns k nt k (n j k ) σ ns k nt k

where σ ns k nt k is the total number of the shortest paths from n s to n t that involve also nodes of the MIoT not belonging to N k , and σ ns k nt k (n j k ) is the total number of these shortest paths that pass through n j k .

IBC can be considered as an evolution of BC, capable of evaluating inner central nodes taking into account the fact that the network I k is not alone but it is part of a MIoT. As a consequence, if all the paths connecting n s k to n t k include at least one node belonging to networks different from I k but inside the MIoT, then BC does not capture them and considers n s k and n t k unconnected. By contrast, in a more precise way, IBC considers that there may exist one or more connections between them in the MIoT, even if they require the intervention of nodes belonging to other networks.

The second betweenness centrality measure that we propose in this paper is called Soft Cross Betweenness Centrality (SCBC) and is defined as follows. Let n j k ∈ N k be the node corresponding to the instance ι j k of the object o j in the IoT I k . The Soft Cross Betweenness Centrality SCBC(n j k ) is defined as:

SCBC(n j k ) = ns u ∈Nu,nt v ∈Nv,u =v σ ns u nt v (n j k ) σ ns u nt v

In few words, SCBC(n j k ) computes the centrality of a node by selecting only the shortest paths between nodes belonging to different networks. There is no constraint on the node n j k for which we are computing the SCBC. As a matter of fact, n j k could belong either to N u or to N v or, finally, to another IoT of the MIoT different from N u and N v .

SCBC can be considered as an evolution of BC capable of detecting central (in the betweenness centrality sense) c-nodes and i-nodes by taking into account that these nodes do not belong to a single-IoT scenario but that they are part of a MIoT, and this fact can influence the shortest paths considered in the computation of betweenness centrality.

The last betweenness centrality measure we are proposing here is called Hard Cross Betweenness Centrality (HCBC) and is defined as follows. Let n j k ∈ N k be the node corresponding to the instance ι j k of the object o j in the IoT I k . The Hard Cross Betweenness Centrality HCBC(n j k ) is defined as:

HCBC(n j k ) = ns u ∈Nu,nt v ∈Nv,k =u,k =v,u =v σ ns u nt v (n j k ) σ ns u nt v

In few words, analogously to SCBC(n j k ), HCBC(n j k ) computes the centrality of a node by selecting only the shortest paths between nodes belonging to different networks. Furthermore, differently from the definition of SCBC, the node n j k is constrained to belong to a network different from the ones of the source and the destination nodes of the path.

HCBC can be considered as an evolution of BC along the same direction as SCBC. The only difference between SCBC and HCBC is that the latter is capable of detecting central c-nodes and i-nodes linking at least three IoT.

IBC, SCBC and HCBC are capable of overcoming the limits characterizing the classic BC in a MIoT. We remark again that IBC is different from the classical BC because it considers that the corresponding IoT is not isolated but inside the MIoT. Given the complexity of a MIoT, such a specific study can be really useful for several applications.

By contrast, if we want to know the most central nodes in a MIoT, the most suitable choices are SCBC and HCBC. SCBC is capable of highlighting the most suitable nodes which allow the cooperation of nodes belonging to different IoT. The term "Soft" characterizing SCBC is due to the soft restrictions of its constraints.

HCBC, instead, is much more restrictive than SCBC. As a consequence, it detects few nodes presenting very high values of betweenness centrality. In fact, they ensure a high cooperation level in the MIoT because they are linked to a higher number of IoT than the other nodes.

The choice between SCBC and HCBC depends on the application context. For instance, if we consider information diffusion, SCBC is well suited for fast information diffusion. HCBC, instead, is a better choice for spreading information among many IoT, even though the diffusion process will be slower than the one guaranteed by SCBC, because of the reduced number of nodes with a high HCBC.

Experiments

Testbed

We derived our testbed from Thingful4 , a search engine for the Internet of Things supporting the search of data regarding a huge number of existing things, distributed all over the world. Thingful also provides some suitable APIs, which can be used for querying it through a software program and which we exploited for the construction of our testbed. In order to obtain our testbed, we needed to perform several tasks. They are described in detail in [2]. Here, we limit ourselves to illustrate the characteristics of our testbed thus allowing the reader to understand the presented experiments.

Our MIoT consists of 11 IoT, reported in the first column of Table 1. We associated an object with each thing. Since we had 250 things, we obtained 250 objects. 200 of these objects had associated only one instance; 35 of them had associated two instances; finally, 15 of them had associated three instances. As a consequence, we had 315 instances in our testbed, distributed among the 11 IoT of our MIoT, as shown in Table 1. A (necessarily complex) visualization of our testbed is presented in Figure 1. The interested reader can find the corresponding dataset (in .csv format) at the address www.barbiana20.unirc.it/miot/datasets/miot2. The password to type is "za.12&;lq74:#".

Tests

In this section, we describe the tests that we carried out to evaluate the significance of our new betweenness centrality measures in a MIoT and to compare them with the classical betweenness centrality. In our test activity, we adopted the testbed illustrated in the previous section.

We started our experiments considering the top-12 central nodes returned by BC and verifying the rank of the same nodes when the other centrality measures are applied 5 . Obtained results are reported in Table 2.

From the analysis of this table we can clearly observe that BC and IBC return completely different results. In fact, 11 of the top-12 central nodes returned by BC have a rank higher than 200 in IBC. Instead, a good correspondence can be observed between the ranks of BC and SCBC, denoting that BC shows a good capability of finding the most "soft" central nodes in a MIoT. By contrast, there is a very loose correspondence between BC and HCBC. This denotes that BC is incapable of finding the most central hard c-nodes. In conclusion, it seems that the BC's incapability of distinguishing between c-nodes and i-nodes and between c-edges and i-edges leads it to show a behavior (someway similar to the one of SCBC) intermediate between IBC and HCBC.

Then, we repeated the same evaluation for the top-12 central nodes returned by IBC. Obtained results are reported in Table 3. From the analysis of this table we can observe that the ranks returned by IBC and those returned by SCBC and HCBC are totally different. Actually, this was an expected result. However, it is interesting to observe that there is a weak correspondence between IBC and BC, because the top-12 central nodes returned by IBC have a rank between 5 and 95 in BC.

After this, we analyzed the top-12 central nodes returned by SCBC. Obtained results are reported in Table 4. Again, we observe a certain correspondence between SCBC and BC, a totally different behavior characterizing SCBC and IBC and a weak correspondence between SCBC and HCBC. All the previous conclusions are confirmed by the analysis of the top-12 central nodes returned by HCBC, reported in Table 5. Observe, also, in this table the substantial difference between HCBC and SCBC, due to the restriction characterizing the definition of the former.

To further verify our previous conclusions and to quantify them, we decided to apply the Kendall Tau rank distance metric [16]. This is a metric aiming at measuring the differences between two different rankings by counting the number of pairwise disagreements between them. More formally, it determines the number of swaps necessary to make the two ranks equal. The higher its value, the higher the distance between the two ranks.

We computed the Kendall Tau rank distance metric for all the possible pairs of ranks determined by considering the four metrics mentioned above. Obtained results are reported in all of our previous conjectures about the metric characteristics and similarities are confirmed. In fact, we can see that IBC and HCBC are completely different. The same happens for IBC and SCBC. Quite a high difference can be observed for BC and HCBC. A certain (not very high) difference can be observed for BC and IBC and for SCBC and HCBC. Finally, BC and SCBC present the highest similarity.

Conclusion

In this paper, we have presented an attempt to redefine betweenness centrality in a multiple IoT scenario, i.e., a scenario where several networks of smart objects cooperate with each other. We have seen that the classical notion of betweenness centrality, which is well suited for a single IoT, present several weaknesses in this new scenario. Indeed, both if it is applied to one IoT at a time and if it is applied to the MIoT as a whole, classical betweenness is not capable of capturing the specificity of the MIoT scenario. In particular, it does not consider the fact that in MIoT there exist several autonomous networks of objects which cooperate with each other through c-nodes that, therefore, play a key role and should be privileged over i-nodes by a centrality measure operating in such a scenario. Then, we have introduced new betweenness centrality measures and we have discussed their features w.r.t. the classic betweenness centrality. Finally, we have presented some experiments devoted to confirm the inadequacy of the classical betweenness centrality for a MIoT and, then, to show the adequacy of the new measures.

In our opinion, this preliminary paper is a starting point for addressing many challenges in the context of MIoT. For instance, analogously to what we have done for betweenness centrality, it is possible to investigate new forms of centralities specifically suited for a MIoT. Furthermore, we argue that smart objects are becoming more and more intelligent and autonomous, showing a behavior increasingly similar to the one of humans. In this case, it is not out of place to investigate issues like object profiling and object reliability, as well as to define techniques to detect anomalous and possibly malicious behaviors of one or more objects in a MIoT.