Managing communities in decentralised social environments

A Decentralised Online Social Network (DOSN) [1] is an Online Social Network implemented on a distributed information management platform, such as a federation of trusted servers, a P2P system, or an opportunistic network. The decentralisation is geared towards granting more control over private data. Indeed, there is no more a single service provider, but a set of peers that take over and share the tasks needed to run the system. During the last years, several solutions have been proposed by both academic researchers and open source communities [15].

One possible approach to DOSNs is represented by a social logical overlay [9] in which social relationship links between users are mirrored in the application-level communication. Among the possible social overlay models, the Ego Network (EN) model [16] is one of the most important. The EN of a user is made of the user itself, which is also called ego, its direct friends, known as alters, and include the direct connections between the alters. The importance of the EN model comes from the fact that it is a social network model representing a user-centric view of the social network. Being centred on a specific user, it can be used to model the local knowledge that each user has of the network. These characteristics make this model suitable for the definition of DOSNs. Formally, given a social network modelled through a graph \(G=(V,E)\), where V is the set of users, and E is the set of relations between the users, each vertex \(u \in V\) can be seen as an ego and \(EN(u) = \left( V_u , E_u \right)\) is the EN of u where \(V_u = \left\{ u \right\} \cup \left\{ v \in V \vert \left( u, v\right) \in E\right\}\), and \(E_u = \left\{ \left( a, b \right) \in E \vert a = u \vee b = u \vee \left\{ a, b \right\} \subseteq N_u \right\}\). \(N(u) = V_u\) - \(\lbrace u\rbrace\) is the set of adjacent nodes of u. Figure 1 shows an example of EN. On the left, a sample graph is shown. The networks A and B highlight the ENs of the ego nodes 10 and 8, respectively, which are represented by a red node. The ENs contain the alters of the ego node, represented with blue nodes, and the relations among them.

The main motivation that brought developers and researchers to create DOSNs lies in the numerous issues that characterise centralised OSNs, including scalability, dependence on a single service provider, and privacy [1]. In particular, in recent years, the rise and quick development of OSNs has led to two important phenomena: user privacy disclosure and the rapid spread of misinformation. OSNs have become the epicentre through which individual privacy is violated. Most of the current DOSNs proposals approach decentralisation through a P2P network. Diaspora¹, with about 680,000 users, is one of the most successful DOSN currently active and deployed in a decentralised way, such as Mastodon [17]. PeerSoN [18] is implemented as a two-tier system in which the first tier is used for peer discovery and lookup, while the second tier is used for the communication between peers and the exchange of users’ profiles. SafeBook [19] is a particular solution in which the P2P overlay network is modelled by Matryoshkas, which are composed of concentric rings of peers built around each peer. The social overlay guarantees trusted data storage and obscure communication through indirection. LifeSocial [20] is a plugin-based DOSN that proposes a solution to the privacy issue by using public-private key pairs to encrypt profiles. Private data are stored in a Distributed Hash Table (DHT). DiDuSoNet [9] is a trust-based DOSN in which the social overlay is modelled by a Dunbar-based social overlay, limited to 150 trusted users [21]. The proposal is mainly focused on the data availability issue by introducing the concept of Point of Storage (PoS). The peers organise in such a way that each profile has only two replicas set up in trusted nodes.

Even if community detection is an important task in complex network analysis [4, 5], there is no universally accepted formal definition of community. Indeed, a community can be defined as a graph with specific structural properties, or can even be defined as the result of a complex process. At a high level, however, a common notion in the community definition is based on the detection of a set of entities where each entity is closer to the other entities within the community than to the entities outside it [22]. While community detection has been widely studied in static complex networks, the interest is quickly growing also for dynamic networks. This is because dynamic networks better model the dynamic nature of current complex networks such as social networks, economic networks and many more. Indeed, the time-evolving nature of the social networks, especially when considering spontaneous networks arising from p2p/opportunistic contacts makes it even harder to formally define what a community is. A first very abstract definition of dynamic communities has been proposed in [5], where the classical definition of a community as a set of closely correlated nodes is refined by taking into account that the relations between the nodes may change over time.

Dynamic Community Detection (DCD) algorithms can be classified into the following main classes [5]: Instant-optimal Community Detection, Temporal Trade-off Community Detection, and Cross-Time Community Detection. In the Instant-optimal Community Detection class, communities existing at time t are discovered by considering only the state of the network at time t. The network evolution is seen as a series of successive snapshots, each representing the state of the network at a particular instant of time. In the second class, Temporal Trade-off Community Detection, the communities identified at time t depend on the state of the network at all the instants of time less or equal t, possibly up to the initial known state. Finally, the Cross-Time Community Detection class includes all the methods that use all available information, i.e. past, current and future with respect to time t, to identify communities at the instant t. Several approaches concerning the dynamic community discovery have been proposed over the years. An exhaustive survey has been proposed in [5].

Community detection in decentralised networks opens up numerous possibilities, countless scenarios, and multiple challenges to be taken into account. However, many approaches for decentralised community detection are merely just a re-adaptation, in a distributed setting, of the Label propagation [7] approach. For instance, in [23] authors propose a framework that allows an analytical study of the distributed community detection problem. A revised label propagation algorithm is proposed to model some features of opportunistic networks. A simpler approach is presented in [24], where the rule to update the labels of the nodes is based on a similarity metric. This approach seeks to achieve better results in terms of modularity, and to mitigate the wandering community effect. In [25], the authors propose a distributed approach for local dynamic community detection and three implementation variants. In this case, the distributed nature of the algorithm induces a very weak consistency among the nodes of the network. Another important contribution is proposed in [26], where game theory is applied to the problem of decentralised community detection in the scenario of social graphs. [23] proposes an approach, based on the Plant Bisection Problem, for distributed community detection in dynamic networks, targeting the scenario of opportunistic networks. Also, the node clustering problem has been tackled with distributed approaches [27]. A downside of this approach is the fact that it is difficult to deal with node dynamics, i.e. join and leave, because, due to the presence or absence of nodes, the clusters may differ a lot. A common technique to tackle dynamism is to add new nodes to existing clusters and to periodically run from scratch the distributed clustering algorithm.

Other interesting approaches applied to DOSNs are proposed in [28‐30]. In [29] authors study the problem of community detection as a binary classification problem, but they completely disregard the time dimension in their problem. The Propose-Select-Adjust framework presented in [30] is a 3-step framework where each node decides to which community it belongs to, and proposes to neighbour nodes to join it. The approach is suited to detect global communities, but the nodes are oblivious concerning the whole structure of each community, because they make a decision based on their local knowledge. In [28] authors propose a decentralised protocol to detect and manage community structures. Even if the authors say that the approach can be applied to smart environments and to mobile networks, the performances of the protocol show that it is not feasible in such scenarios.

In this paper, we propose an innovative, fully decentralised approach for local community detection in DOSNs called DISCO. Contrarily to other approaches presented in the literature, we take into account the possible presence of mobile devices, and for this reason, we consider a definition of community in line with the distributed environment. We also take into account the specific scenario of application of our protocol, by detecting a community structure that is local with respect to the users of the DOSN. DISCO also introduces a load balancing mechanism, to make sure that the community detection burden is almost uniformly spread among the nodes of the network. Nodes participating in DISCO adopt a proactive behaviour, meaning that they will constantly monitor the community structure around them, and make sure to set up or dismiss communities as needed.

Above the communication layer and the DHT, we use a social overlay network to store private data. A Social Overlay, as introduced in [33], is an overlay where nodes are only connected to each other if a social tie exists between them. This kind of overlay can be considered a F2F overlay in which users only make direct connections with people they know. Our Social Overlay is structured by using the EN model, as explained in Sect. 2.1. For sake of readiness, each peer has its EN and the union of all EN composes the social overlay (see Fig. 1). Each peer maintains a local view, in which there is information about its direct social contacts. Indeed, nodes are connected to known nodes, and an edge between a pair of nodes indicates a social relationship between them.

The representation of the local knowledge through the EN model permits us to maintain information about all the social connections which can involve the ego: links between the ego and another user (alter) and links between alters of the ego node. Our network model is inspired by the Dunbar Social Overlay presented in [9].

Our protocol uses a super-peer approach [34] where super-peers are in charge of executing the DCD algorithm. In DISCO, when the ego e is online, its node is responsible to manage the communities of its own ego network. Instead, when e is offline, the management of its communities is assigned to a set of super-peers, which are chosen from its ego network. In our approach, these super-peers are named moderators, and will be in charge of keeping communities updated as other nodes join and leave the network. Moderators, each time a node joins or leaves the network, re-evaluate the set of communities they manage and, if certain conditions are met (explained in detail in Sect. 4), modify them, interacting with the nodes belonging to them.

To be sure that moderators can function properly, we assume that they know the EN structure of the egos on behalf of which it is moderating at least a community. We safely make this assumption because the ego network structure of a node can be easily retrieved by current community moderators. The EN structures can also be exchanged between two nodes when they first add to each other’s EN, and can be cached and used when needed. Overall, each node has to store the subgraph that contains only their 2-nd order neighbours, which is a reasonably small portion of the whole P2P network. Knowing the EN structure allows moderators to efficiently evaluate whether a joining node can be part of the community, and to reduce the number of communication costs when a node leaves the network.

Each community has two moderators. Indeed, having a single moderator for each community has important drawbacks. The main drawback is connected to the nature of super-peer approaches, which are fragile in case the super-peer fails unexpectedly. For this reason, we manage communities with both a primary moderator and a secondary moderator. The secondary moderator acts as a common peer and, as the only addition, runs a ping-pong protocol with the primary moderator. Indeed, the secondary moderator is a backup moderator, taking the role of the primary moderator in case it detects that the current primary moderator of the community has failed (through the ping-pong protocol). When the secondary moderator detects the failure of the primary one, additionally to promoting itself as the primary moderator, starts a procedure to re-establish consistency, electing a new secondary moderator for that community, and updating the community metadata stored in the DHT. We do not consider using more than two moderators, because we suppose that the procedure of electing the secondary moderator is completed before a new failure happens.

In Fig. 3, we show an example with three communities in two different ego networks. The first ego network, whose ego node is represented by the blue node labelled as \(E_1\) and whose members are blue, has two active communities (\(C^1_1\), and \(C^2_1\)), while the second ego network, whose ego node is represented by the red node labelled as \(E_2\) and whose members are red, has a single active community (\(C^1_2\)). Purple nodes belong to both communities. Each ego node is connected to the respective alters with dashed lines. In this scenario, the community \(C^2_1\) has a primary moderator the node identified by the white letter ’M’. Communities belonging to different ego networks can have the same node as moderators, as the purple node identified by the black letter ’M’, which is the primary moderator for both \(C^1_1\) and \(C^1_2\). They are computed by considering the ego minus ego network (an EN where the ego node is removed). The ego node is not considered in the community detection task because it may collapse the community structure since it is connected to all its alters by definition.

Adopting a moderator approach can bring additional benefits. In particular, we can assign further responsibilities to a moderator. For instance, if we consider the privacy problem, the moderator can be the one that enforces the privacy policy assigned to that community. Furthermore, if we consider that information shared inside a community can be replicated in its nodes [12], the moderator may also decide the allocation of the shared information on the nodes of the community. Finally, the presence of super-peers simplifies the protocols to guarantee consistency in shared information.

As presented in Sect. 3, in the reference architecture we consider the presence of a DHT layer implemented by Pastry [31]. Several DOSNs proposals use the DHT as the underlying layer, since it allows to retrieve information about the nodes in the network, and it can help to support data availability [18, 20, 35, 36] and privacy.

In DISCO, the DHT is only used as a support layer for our DCD algorithm, while private users’ data are stored using a different technique. One such example is to let the peers of the social overlay organise themselves to create social data replicas, as explained in [9]. This enables to keep a high level of privacy, without incurring in the usage of other techniques to enforce privacy, such as cryptography. In our approach, the DHT is used to store community meta-data, and as an entry point for the joining nodes to discover which nodes are the moderators of the communities. To let joining nodes easily discover the moderators of communities of an ego e, DISCO uses the id of the ego as the key of the DHT. The value corresponding to a key id is the set of moderators of the currently alive communities in the ego network of the ego identified by id.

As discussed in Sect. 2, DCD algorithms can be classified as: Instant Optimal, Temporal Trade-off and Cross-time. The three classes differ in the amount of information used to carry on the task, which deeply affects the usability in different contexts.

Cross-time algorithms detect communities at a given instant of time t using all the possible information available, namely the state of the network at any point in time. The great limitation of this class is the fact that it requires to access future information, with respect to the instant of time t when the communities are detected. In DISCO, communities have to be computed online, in real-time, and information about events happening after t, is not available, like in an off-line system. This fact makes this class completely unfeasible in our scenario.

In the Instant optimal class, detection of communities at the time instant t only uses the state of the network at t. This class uses a minimal amount of information and the definition of the algorithms is, therefore, simplified. The problem with this class lies in the fact that communities must be detected from scratch each time they are needed, which is a limitation imposed by the information used to carry out the community detection task. Indeed, a snapshot of the network must be collected somehow in order to start the detection of the communities. And, while this doesn’t seem a big problem in scenarios where powerful machines are employed in the detection task, it may represent a serious drawback in decentralised, P2P architectures with heterogeneous, low-end devices. The main problem comes from the fact that obtaining a consistent and updated snapshot of the network is a hard task in distributed systems, where each node has limited knowledge of the network and node churn is an impactful phenomenon. The scalability of the system may be highly affected by such an approach: in fact, it is not feasible to make one node collect the snapshot of the network and then detect communities in a large scale network. A mechanism that distributes the community detection ask, will introduce heavy synchronisation phases. For these reasons, the Instant Optimal class of algorithm is not well suited for our scenario.

In conclusion, we decided to choose an approach belonging to the Temporal Trade-off class, because of the better chances to obtain an efficient and scalable solution. The two key features of our approach emerging from this choice, are the ability to update communities locally and independently to one another, and the possibility to update communities, rather than computing them from scratch each time.

Dynamic communities are characterised by the so-called life-cycle events, which correspond to critical events.

We consider the following events:

In this Section, we introduce the algorithm used by the moderators to manage the communities. It is used by each moderator when it receives messages from the nodes joining/leaving an EN, which are used to update the communities. The protocol executed by the peers will be described in Sect. 5.

DISCO uses two structures for the definition of a community, triangles and triads. Let us consider a community C and a new node n. n can be added to C if and only if at least one of the following conditions is satisfied:The triangle condition aims at keeping a high level of clustering among the nodes inside the community. The neighbour condition aims at softening the triangle condition, making nodes that are well connected to the community join it, even if they do not close a triangle. What we expect is that a well-connected node n will close more and more triads over time, so defining more and more triangles and increasing the clustering coefficient of the community, even if the insertion of n has lowered it temporarily. This fact should also bring to a situation where the number of communities is sensibly lower because a node is more easily accepted into existing communities.

Last but not least, the neighbour condition is also computationally less expensive with respect to the triangle one. Indeed, it only requires counting the number of neighbours of n that are inside C. Furthermore, in a DOSN scenario, it will often happen that whenever the triangle condition is satisfied, also the neighbour condition is satisfied.

Let us now discuss what happens when a node n is eliminated from a community. The very first step to handle the departure of n is to remove the node from the community itself and the following step is a check for membership for a subset of nodes inside the community which are involved in the departure of n. Rather than checking all nodes in the community which can be computationally very expensive even for small communities, the check is performed only for the neighbours of n, sensibly reducing the number of controls to be made. The procedure for node checking is as follows. The nodes to be checked are labelled as unconfirmed (Fig. 5b). Then, any unconfirmed node is considered, one by one, and DISCO verifies if either joining condition holds for that node, i.e. the triangle and the neighbour conditions. If either of the conditions holds, that node is labelled as confirmed and excluded from further checks. This verification process is repeated until no more nodes can be labelled as confirmed. At this point, all unconfirmed nodes are removed from the original community, while all confirmed nodes will remain inside the community (Fig. 5c).

After the check for membership process has finished, the original community can be split into several shards, where each shard may contain one or more nodes. To detect these shards, the connected components of the graph resulting from the removal of the leaving nodes are computed. Each of the resulting components is a new standalone community. As we will see in the next Section, if required, the moderator will notify the peers involved in the community update so that they can self-organise in new communities.

In the case of a node n joining an EN of a node e as an alter, the aim of n is to get accepted into an existing community within the EN of e. In order to do so, it obtains the list of active moderators of the EN it is joining to from the DHT, and, upon receiving this list, it sends a join request to each moderator. Thanks to the fact that the moderator knows the EN of the ego for which it is moderating the community, it can check if the requesting node can join the community autonomously, without the intervention of the moderator. Moreover, the joining node pings all its alters to check which of them is online, in case a new community needs to be defined from scratch. Finally, a timeout is set to restart the joining procedure in case it fails. When the reply from the DHT containing the list of moderators for the ego network of e is received, the joining node contacts them to notify it is now online and to ask to be part of the communities managed by the moderators. A moderator, upon receiving a notification from a joining node evaluates the connections among the joining node and the other nodes inside each community managed by it, evaluating whether the new node may be inserted in that community. The set of conditions, defined to insert a new node in an existing community, are those described in Sect. 4. According to the results of this evaluation, a message is sent back to the joining node to notify it whether it can be inserted in the community or it cannot join the community because the joining conditions are not satisfied. In the first case, the moderator updates its community accordingly. In Fig. 4, we show the join procedure executed by nodes A, B and C, with the messages exchanged between each of them and the moderator of a community.

It may also happen that a node cannot join any community. This may happen if, for instance, up to now no community has yet been created, and therefore no moderator has been elected. In this case, the joining node can detect if a new community can be built around itself, collecting information about its neighbours through the ping process, as explained in the following section.

As last resort, if a node cannot join any community, because no communities are defined or none of the existing communities can accept it, the node will try to create a community on its own with itself as a moderator. This corresponds to a community birth event. As explained in Sect. 5.1, when a node joins the network, it also pings its neighbours on the social overlay. Indeed, thanks to the information received from the online neighbours, a node is able to detect whether a community structure is forming around it. Upon receiving replies from its neighbours, the node checks if there is at least a triangle of online nodes including itself. After having detected all the triangles with the online neighbours, the node creates the communities, merging in the same community the triangles sharing at least an edge. Note that the triangle remains the basic structure to create a new community, while the triangle condition is relaxed in the join/leave operations. When the community has formed, the node that discovered a community structure around it becomes the primary moderator for that community. Right after, the newly self-proclaimed moderator elects a secondary moderator by choosing, uniformly at random, a node among the nodes belonging to the newly formed community. To complete the joining process, it also inserts in the DHT the information about this newly formed community, along with a reference to the two moderators, so that the nodes joining the network in the future, will be able to retrieve it, as explained in Sect. 3.3. As the last step, to complete the community birth, all the nodes inside the community are notified of its birth.

Note that this method can fail in the bootstrap phase, when there are no communities because the system contains less than three nodes or the nodes are not well connected. For this reason, if all previous procedures fail, the node set a timeout and, when it expires, it re-executes the whole node join procedure.

A node voluntarily leaving the network should inform the primary moderator of the communities it is part of that it will be unavailable soon. Since each node stores a reference to these moderators, the overhead to leave the network is minimal.

When the moderator receives the message from a leaving node n, it has to reevaluate the roles of all nodes in the surrounding of the leaving node. The moderator removes the leaving node from the community, and then determines if its departure modifies the community structure, executing the membership tests explained in Sect. 4.3. Note that, since the moderator knows the EN n belongs to, no additional input is required. All nodes which are unverified (see Sect. 4.3) will be removed from the community and will get a notification from the primary moderator, while all verified nodes will remain inside the community (Fig. 5c). This notification allows the unverified node to try to join other communities if the unconfirmed node realises belong to any of the communities.

After this process, the community can simply shrink in size if the departure of the leaving node has not produced a split of the community. A more impactful scenario is when, after a node leaves the network, the community is divided into shards. If the current primary moderator still belongs to one of the shards resulting from the split, this shard inherits the original community and the corresponding primary moderator. All the other nodes will receive a message from the primary moderator stating that they are no more part of that community.

At the same time, each shard of the original community is now a community of its own and will have both primary and secondary moderators. To this aim, the primary moderator of the original community elects uniformly at random a primary moderator among all the nodes inside the new community (Fig. 5d). The primary moderators of the created shards, independently of one another, are in charge of notifying all the nodes in their respective shards about their identity, and adding a reference to their own shards in the DHT, so those other nodes can find and join the community of that shard. Furthermore, each newly formed community will be entrusted to the respective newly elected moderator which is now in charge of electing a secondary moderator for its community. Note that the original community can also be completely destroyed and this corresponds to a death event.

The departure of a node may cause more nodes to also be removed from the community and from each one of its shards. These nodes that end up being outside the community (as a consequence of the node leaving the network) will be notified by the primary moderator of this event. In particular cases, this may lead to a situation in which one (or more) nodes are still online and available but they are not inside any community. A node in this situation will try to re-establish a regular situation, trying to become part of a community as if it just joined the network. The fact that a node actively tries to always be part of a community is a peculiar property of our approach. Indeed, many DCD algorithms in the literature are just data mining tools in which nodes try to join communities only when they switch their status to online. Instead, our approach enables nodes to actively search for new communities when they don’t have one. Although this is a parameter of DISCO, for the remainder of the paper we will consider that nodes will try to be part of at least one community.

If a primary moderator voluntarily leaves the network, it also must take care of the communities it has managed up to now. Such communities need another primary moderator and the community must be updated according to the procedure we described in Sect. 4.3. We decide to perform the election of the new primary moderator in the old primary moderator, or rather, the node that is leaving the network, and we decide to perform the update of the community in the new primary moderator. The election of the new primary moderator can be performed rather quickly and each community must have one. On the other hand, the update of a community structure can be a quite lengthy process, and we do not want the old primary moderator to do extra work which can be done by the new primary moderator. The strategies we considered for the election of a primary moderator are presented in Sect. 5.4.1.

The case of a secondary moderator leaving the network is simpler. The primary moderator elects a new secondary moderator, updates the DHT, and finally manages the leave of the secondary moderator as a normal node. The strategies we considered for the election of a secondary moderator are presented in Sect. 5.4.1 as well.

Finally, a moderator can also fail unexpectedly. To cope with this possibility, as we introduced in Sect. 3.2, we suppose that each pair of primary and secondary moderators of the same community run a ping-pong protocol. Thanks to this approach, the two moderators can detect each other failure in a timely, and then perform the required actions to reestablish the optimal situation with the two moderators.

To have an evaluation that is the closest possible to a real-world scenario, we decided to use a dataset based on real users. The dataset was gathered on the popular OSN Facebook through an application called SocialCircles!. The application was developed and deployed in 2014, but is now under maintenance since the 1st of May 2015. This was because Facebook considerably reduced the size of its APIs, denying the necessary support for the correct functioning of the application.

As presented in [41], the application was able to retrieve three sets of information:During its lifetime, the application was able to gather two datasets. In this work, we use the second one which includes 240 registered users, and 32 days of observation.

The dataset is made of 240 registered users, for a total of 78.129 users observed, if we consider also the friends of the registered users. To execute our experiments, we used the topology information available, namely the EN of the 240 registered users, and the temporal information. The temporal observations lasted for 32 days, from the 9th of March 2015 to the 10th of April 2015. As result, we got a total of 9251 boolean observations for each of the 78.129 users: the value true in the i-th observation corresponds to the user being online during that observation.

The first preliminary observation concerns the temporal behaviour of users over the social network. Given the fact that we tackle the community detection problem in a temporal fashion, it is fundamental to have a deep understanding of the temporal information in our possession. We start by analysing which are the common trends of the temporal behaviour of all users both in terms of when to expect a large number of online users and which are the typical session of users.

Before presenting the results of our analysis, we briefly make an overview of the temporal information in our possession. In our dataset, time is discretised because of the restrictions imposed by the Facebook API. As described before, we made 9251 observations, once every 5 minutes, of the EN of the registered users, thus obtaining 9251 observations for all the 78.129 users. We can consider each observation separately, giving an observation of the state of the network at that particular time. For this reason, we will henceforth address the time of these observations as time slots. Observing the status of a user via the Facebook API returned an integer value: 0 if the user was offline, 1 if the user was online and 2 if the user was idle. For the sake of our work, we turned this integer value into a boolean value using the following translation formula:where \(s(u)_i\) denotes the status we store for user u at time slot i, and observation is the value observed via the Facebook API.

After the preliminary temporal study, we present a comparison between SONIC-MAN [28] and DISCO. The two protocols are simulated using PeerSim [42], an open-source P2P simulator written in Java. This choice was made because PeerSim is capable of simulating nodes with up to a few million nodes, network delays can be modelled easily, and it supports an event-driven simulation.

As a final analysis, we made some analysis on the number of the messages exchanged by the two protocols used in the simulation: our implementation of Pastry, and DISCO. In this showdown, we will compare the number of messages for both the protocols, dividing each time these messages into three sets, according to their role in the protocol. We will also make some final considerations about the total number of messages.

In this last Section, we analyse what is the impact of the newly added mechanism of load balancing. In order to make a fair comparison, we evaluate the number of messages moderators receive for the management of the communities. In the case of the older approach SONIC-MAN, which does not have a load balancing mechanism, we only consider the JOIN and LEAVE messages. Instead, in the case of DISCO, we consider not only the JOIN and LEAVE messages, but also the periodic messages node send to their moderators to notify their load factor. This set of messages was presented in Sect. 6.4.1 as the Generic node messages. This should help us to estimate the increased amount of communication required for the added mechanism to work.

Figure 28 shows the average number of messages moderators receive as part of their duty, as discussed above, in reading for SONIC-MAN and in green for DISCO. Results are deseasoned showing aggregated average values for 288 timeslots, which is the number of timeslots in a day. From the plot, it emerges that until day 13 the two approaches put a similar burden on the moderators, but on average moderators in DISCO are slight more loaded. This is mostly due to the cold start of the load balancing mechanism which requires some more messages to start working properly. However, from day 14 and onward we clearly see that the burden of messages on moderators of SONIC-MAN is 25% to 50% higher. This difference is due to two effects: a steep increase in the number of messages handled by SONIC-MAN moderators starting from day 14 and a slightly decrease over time in the number of messages handled by moderators of DISCO. Taking a closer look at the logs, we observed that in SONIC-MAN, the number of JOIN messages heavily increased after day 13. Trying to understand what is causing this abnormal amount of messages, we looked at the overall community structure of the approach shown in Fig. 10. Indeed community structure is unstable in terms of the number of communities around day 13 (which is made of the timeslot from 3456 to 3743), and this effect is also present later on during the experiments. Further analyses of the logs, showed that in SONIC-MAN a lot of nodes were not able to join any community for several timeslots from day 13 and onward. Since nodes will actively try to be included in at least one community, this can cause a lot of messages to circulate at each time slot if multiple nodes are not able to find a community. In the case of DISCO, we do not see a similar instability in the community structure, nodes are not required to try again to send messages to join a community, and therefore moderators result in having to handle a smaller number of messages on average. The logs of the experiments uncover that in this case, nodes are usually able to join or create a community right when they join the network, rather than having to wait for several timeslots. Therefore we can conclude that the updated algorithm for community detection, and in particular the new condition explained in Sect. 4.3, resulted in an accidental optimisation of the communication required, despite the added load balancing mechanism.