Barbara Guidi
email: guidi@di.unipi.it

Andrea Michienzi
email: andrea.michienzi@di.unipi.it

Laura Ricci
email: ricci@di.unipi.it

SONIC-MAN: a distributed protocol for dynamic community detection and management

Keywords: Peer to Peer, Community Detection, Complex Networks, Decentralized Online Social Networks

The study of complex networks has acquired great importance during the last years because of the diffusion of several phenomena which can be described by these networks. Community detection is one of the most investigated problem in this area, however only a few solutions for detecting communities in a distributed and dynamic environment have been presented. In this paper we propose SONIC-MAN, a distributed protocol to detect and manage communities in a peerto-peer dynamic environment. Our approach is particularly targeted to distributed online social networks and its main goal is to discover communities in the ego-network of the users. SONIC-MAN is based on a Temporal Trade-off approach and exploits a set of super-peers for the management of the communities. The paper presents a set of evaluations proving that SONIC-MAN is able to detect dynamic communities in a distributed setting and to return results close a centralized approach based on the same basic algorithm for community discovering .

Introduction

Today, several important real life networks, such as those defined by social relationships, cryptocurrency transactions, biological systems, etc., are modeled by graphs. Due to the huge size of these graphs, their study requires novel methodologies, which are investigated in the research area referred as complex network analysis. Several algorithms and tools have been developed, mainly conceived in a centralized way.

However, in recent years we witnessed a dramatic shift from fully centralized applications to completely or partially distributed applications. One of the applications which have recently benefit from this shift are Online Social Networks, for whom a set of distributed proposals, i.e. Distributed Online Social Networks (DOSNs), have been recently presented. Implementing the social services in a distributed fashion is the key point of addressing well known problems, such as the scalability of the service and, most of all, the possibility for the users to gain more privacy over their data. On the other hand, this scenario rises several challenges, such as data availability and information diffusion, mainly regarding the dynamic nature of the network.

One well known concept in the field of the social network analysis is the community detection, which is one of the most investigated problems in this area. Being able to group entities according to some rule, can be exploited to address many problems.

Many centralized algorithms [START_REF] Fortunato | Community detection in graphs[END_REF] have been proposed for community detection, mainly based on different definitions of community. However, only a few proposal of distributed algorithms/protocols have been presented till now, even if the concept of community is useful for several problems arising in distributed scenarios, for instance to guide information diffusion in P2P networks, mobile or opportunistic networks. In particular, in the DOSN scenario, detecting communities in the ego networks of a node may support data replication strategies exploited to guarantee a high level of data availability. In these scenarios, it is necessary to define a distributed protocol to maintain and manage communities, in presence of an high level of dynamism of the network.

In this paper we propose SONIC-MAN, a distributed protocol for dynamic community detection and management targeted to DOSNs. The main characteristics of SONIC-MAN is the presence of a set of super-peer nodes whose goal is the management of the communities discovered in the ego network of a node. Several current approaches re-adapt existing community detection algorithms, such as the Label Propagation [START_REF] Raghavan | Near linear time algorithm to detect community structures in large-scale networks[END_REF], in a distributed fashion. Instead, our approach relies on a set of super-peers, which apply a sequential algorithm for detecting communities and synchronize among themselves to maintain communities consistent. Our approach exploits the triangle as community model and uses a Temporal Trade-off approach [START_REF] Rossetti | Community discovery in dynamic networks: a survey[END_REF] to manage the evolution of communities. The main novelty of our approach is that, while current approaches are conceived mainly in the field of data mining, our solution is better suited in a distributed system to discover and manage communities varying over time.

The paper is organised as follows. In Section 2 we describe the state of the art and related works. Section 3 contains the walkthrough of our approach and the results of our experiments are presented in Section 4. Finally, in Section 5, we conclude this paper and we point out some of the future works.

Related work

In this section we introduce the state of the art concerning the topics treated in this paper, starting from an overview on DOSNs, then presenting the main concepts of Community Detection, and finally concluding this section with a quick survey of Decentralized Community Detection.

Distributed Online Social Networks

A Distributed Online Social Network (DOSN) [START_REF] Datta | Decentralized Online Social Networks[END_REF] is an online social network implemented on a distributed information management platform, such as a network of trusted servers, P2P systems or an opportunistic network. During the last years, DOSNs have been argument of several works from both academic researchers and open source communities. By decentralizing OSNs, 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. In this contexts, social relationships are represented by a logical overlay, named social overlay [START_REF] De Salve | Evaluation of structural and temporal properties of ego networks for data availability in dosns[END_REF]. In a social overlay, a connection between two users means that these users are friends. A common way to model the social overlay is through the concept of Ego Network (EN) [START_REF] Everett | Ego network betweenness[END_REF]. The ego network is a Social network model that can be adapted in a P2P environment because it represents a user-centric view of the network, and it can be used to model the local knowledge of the network an ego has. An ego network is made of the user itself, which is also called ego, its direct friends, known as alters, and also include information about the direct connections between the alters. Formally, given a social network modeled through a graph G = (V, E), where V is the set of vertices and E is the set of relations connecting the nodes, each vertex u ∈ V can be seen as an ego and

EN (u) = (V u , E u ) is the ego network of u where V u = {u} ∪ {v ∈ V | (u, v) ∈ E}, and E u = {(a, b) ∈ E|a = u ∨ b = u ∨ {a, b} ⊆ N u }. N (u) = V u
{u} is the set of adjacent nodes of u. In Figure 1 an example of ego network is shown. On the left an example network is shown, on the right the ego network of two nodes is highlighted: the ego, represented by a red node, its alters, represented with blue nodes, and the relations among them.

Community Detection

Even if community detection is an important task in complex network analysis [START_REF] Aynaud | Communities in evolving networks: definitions, detection, and analysis techniques[END_REF][START_REF] Cazabet | Dynamic community detection[END_REF], no common definition of community is currently available. However, each notion of community 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 [START_REF] Coscia | A classification for community discovery methods in complex networks[END_REF]. While community detection has been widely studied in static 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. In this case, it is even harder to formally define what a community is. A first very abstract definition is proposed in [START_REF] Rossetti | Community discovery in dynamic networks: a survey[END_REF], where a community is identified with the sets of closely correlated nodes considering the fact that the relations between them may change over time, thus changing the communities.

Dynamic Community Detection algorithms can be classified into the following main classes [START_REF] Rossetti | Community discovery in dynamic networks: a survey[END_REF]: Instant-optimal Community Detection, Temporal Trade-off Community Detection, and Cross-Time Community Detection. In the Instantoptimal 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 instant of time less or equal t, possibly up to the initial known state. Typically communities are discovered by an iterative procedure which consist of an initial bootstrap, which yields the existing communities when the observation starts, followed by a set of successive updates to these initial communities. 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 instant t.

Decentralized Community Detection

Some studies about community detection or node clustering, in dynamic P2P networks have been recently presented. Many of these approaches are basically just a re-adaptation, in a distributed setting, of the Label propagation [START_REF] Raghavan | Near linear time algorithm to detect community structures in large-scale networks[END_REF] approach. For instance, in [START_REF] Clementi | Distributed community detection in dynamic graphs[END_REF] authors propose a revised label propagation divided in five phases, each of which has a different rule to update the labels of nodes. A simpler approach is presented in [START_REF] Herbiet | Sharc: Community-based partitioning for mobile ad hoc networks using neighborhood similarity[END_REF], where the rule to update the labels of the nodes is based on a similarity metric. In [START_REF] Hui | Distributed community detection in delay tolerant networks[END_REF], 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. Also, the node clustering problem has been tackled with distributed approaches [START_REF] Ramaswamy | A distributed approach to node clustering in decentralized peer-to-peer networks[END_REF]. 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.

A novel distributed protocol for dynamic community detection

In this section we present the protocol SONIC-MAN (SOcial dyNamIc Community MANager), our distributed solution targeted to the detection of communities in the ego networks of a DOSN. Contrary to the works present in literature, the approach defined in this paper is not a re-adaptation in a distributed fashion of another well-known approach and adopts a pure Temporal Trade-off approach. Moreover our approach guarantees a consistent view of the communities through all the nodes in the network, making them more usable in the development of distributed systems.

Our protocol is built on top of a 2-tiers architecture, described in [START_REF] Guidi | Didusonet: A P2P architecture for distributed dunbar-based social networks[END_REF]. The DHT, which implements the lowest layer, is used as look-up service to store information about super-peer nodes, which are managers of the information about the communities. The topmost layer is a logical social overlay modeled through an ego network [START_REF] Everett | Ego network betweenness[END_REF]. The ego network is a well-known social network model used to represent user centric networks. Indeed, the ego network of a node is the subgraph of the whole network considering only the node itself, its neighbours and all the edges between these nodes.

An overview of SONIC-MAN

We investigated the design of an approach to support dynamic community discovery in ego network of DOSNs, and, as suggested in [START_REF] Guidi | Dynamic community analysis in decentralized online social networks[END_REF], our natural choice for the distributed community detection has been the Temporal Trade-off one. This choice was driven by the fact that the other two approaches do not naturally fit a dynamic distributed scenario. Cross-Time CD is not usable in principle due to the fact that the results of the algorithm are needed while the system lives, so future information is not available. Instant-optimal CD has the major issue connected to the need of a separate mechanism to match communities discovered at each time instant which may lead to wrong matchings. Another major downside of Instant-optimal CD is the fact that each time communities must be detected, we need the current snapshot of the network. This results in having synchronization, or strong consistency, between nodes, which is difficult to obtain in distributed asynchronous systems [START_REF] Fischer | Impossibility of distributed consensus with one faulty process[END_REF].

SONIC-MAN may be exploited to discover and manage the communities within the ego network of a node of a distributed online social network. The protocol considers the dynamism of the communities, due to the fact that nodes may autonomously change their presence status from online to offline, and viceversa.

The algorithm is executed by the nodes of the social network themselves and exploits a set of super-peers, chosen among the nodes of the ego networks, which execute a Temporal Trade-off algorithm and maintain the discovered communities. The management of communities is essential due to the fact that dynamic communities show a life-cycle during their evolution, which is characterized by a list of events [START_REF] Cazabet | Dynamic community detection[END_REF][START_REF] Palla | Quantifying social group evolution[END_REF][START_REF] Takaffoli | Modec-modeling and detecting evolutions of communities[END_REF]. In a distributed environment, these events are generated by the temporal behaviour of nodes and they affect the structure of the ego network, as explained in [START_REF] Guidi | Dynamic community analysis in decentralized online social networks[END_REF]. Within each community we identify one peer which leads and manages the community. In particular, this super-peer, called moderator of the community, can decide which nodes belong to the community, following a set of rules explained later in this section. Considering both the high dynamism and the possibility to have involuntary disconnections, we introduce a secondary moderator which acts as a normal peer, while the primary moderator is up and running. In all the cases a new secondary moderator is needed, it is elected by the primary moderator, choosing at random a node inside the community. The two moderators execute a ping/pong protocol to detect each other failures. When a failure is detected, the secondary moderator takes the role of the primary moderator. SONIC-MAN exploits a DHT to store information about moderators of active communities, so joining nodes may discover moderators of the communities of the ego networks.

Each moderator maintains a copy of the ego network of each ego for which it is moderating at least a community. This design choice is made to allow the moderator to iterate the evaluation of the communities when some event occurs, so avoiding to repeat the access to the community structure and saving a huge amount of communication.

Assuming that a moderator knows the ego network for which it is maintaining a community, we can also make very strong assumptions about the structure of the graph which represents the current state of the network. When a node enters or leaves the network, each moderator has the possibility to update each community that node belongs to. Indeed, when a node joins an ego network, the moderators can detect if the joining node belongs to the communities they manage by knowing only the identity of the node. This is because they know to whom the joining node is connected inside the ego network and who are the nodes inside the community.

In this work we decided to adopt a triangle-based community model. A node, to be accepted inside a community, must close a triangle with two other nodes already inside the community. This choice helps in having tight and clustered communities, and, at the same time, avoiding building communities made of chain-like structures. The same model is used in TILES [START_REF] Rossetti | Tiles: an online algorithm for community discovery in dynamic social networks[END_REF] or in the 3-cliques percolation methods, and they are all linked to the concept of clustering coefficient.

A walkthrough of SONIC-MAN

In the following, we describe in detail the expected behaviour of a node running SONIC-MAN when it joins the network. An important point is to keep in mind that each node is, at the same time, ego for its ego network and alter for the ego networks of its neighbours in the social network.

Node join A node joining the network, after joining the DHT, must undertake two independent actions: 1. Join the active communities belonging to the ego networks of its alters; 2. Retrieve the active communities belonging to its ego network.

Algorithm 1 shows the steps needed to complete the first action. For each of its alters a (which are also ego of their respective ego network), the joining node n firstly searches in the DHT for the moderators of a, then it notifies all the moderators of a that it is now online (line 2-3). The joining node then sends to the moderator the identity e of the ego networks it is joining to (as alter), because each moderator can manage the communities of a set of ego networks. Finally, if the moderator m inserts the joining node in a community, the joining node records the identity of the moderator.

The moderators will update each community based on the nodes inside the community itself and how they are connected to the joining node. It is important to highlight that, in the Temporal Trade-off algorithm used by SONIC-MAN, to enter a community, a node must be involved in at least a triangle with two different nodes that are already inside the community. However, this behaviour is customizable, and can also be different from node to node. If the updated community contains the new node, its moderator will notify the joining node that it is part of its community for that particular ego network. An online node also periodically checks that it is still in a community for each of its neighbours. If it finds out that it is lacking some communities, it tries to build one using the Algorithm 2. The node pings all its neighbours which also belong to the ego network for which a community is missing (line 4). Then, after a fixed timeout, it tries to search for triangles (line 7) among its online neighbours. If one is found, the community is formed (line 8). Upon the birth of the community, the node itself become the primary moderator and it is in charge of updating the list of the moderators in the DHT and notify all the nodes inside the community that a new community is formed and that it is the primary moderator (line 9). If, instead, no triangle is found, the node waits for a timeout and then repeats the process, until a community is found for that particular ego network. It may be the case, if very specific conditions are met, that two nodes build the same community for the same ego network at, roughly, the same time. As stated later in this section, moderators periodically check whether communities can be merged together. This case falls inside the general case of the merging of two communities.

Algorithm 3 shows the sequence of the actions that an ego must do to retrieve the communities in its ego network. Even if this is not strictly necessary, because communities could still be managed by the moderators or even destroyed while the ego is online, it is desirable for the ego to maintain the communities by itself even if it is online. In this way, when the ego leaves the network, the communities have not to be reconstructed from scratch so avoiding an overhead and smoothing the communities over time. To retrieve its communities, the ego searches in the DHT for the moderators of such communities (line 2), then it notifies the moderators it is now online and sets itself as the only moderator for its ego network (line 4). The moderators will send to the ego the community they are managing and will stop manage it right after. Node leaving When a node leaves the network it has to undertake actions for each of the communities it is part of and for each of the communities it is moderator of. When the node leaving the network is just a simple node, not a moderator, it just sends a message to the moderators of the communities it belongs to, notifying them that it is going offline, which, in turn, update the structure of the community. When a node leaves the community, the moderator builds sets of adjacent triangles (sharing two nodes), called triangle components. A triangle component is defined as a set of nodes which forms triangles which share at least one node in twos. For each of the triangle component a new community is created and a new primary moderator is elected for each of the new communities, while all members are notified that the community is no more. The new moderator, upon receiving the community, notifies the nodes inside that it is a moderator of a new community and adds an entry in the DHT. If the leaving node is a primary moderator, it informs the secondary moderator it is leaving and stops managing the community. The secondary moderator promotes itself as primary moderator, it elects a new secondary moderator and updates the DHT. Then it updates the community roles and tells all the community members it is the new primary moderator. Finally, if it is the secondary moderator of a community that it is leaving the network, it has to inform the primary moderator it is leaving. The primary moderator elects a new secondary moderator, updates the community roles and updates the DHT as well.

A special case of node leaving is the failure of nodes. Whenever the primary moderator discovers that a node inside its community failed, it is its duty to update the community roles as if the node voluntarily left the network. It is worth to point out that if the failed node is the secondary moderator, the primary moderator also has to promote a node to secondary moderator. The node failure may be discovered by the primary moderator by itself, by pinging the nodes inside its community, or by a clue coming from the other nodes inside the community. One last case is the one where the primary moderator itself is the failing node. In this case, the secondary moderator should discover this event because each pair of moderators of a community run a ping/pong protocol. The secondary moderator can treat this situation as a voluntarily leave of the primary moderator.

Community merging

The community merge event is a non trivial event because it requires to detect the communities which have to merged. For this reason, periodically, a synchronization phase between moderators is executed with the main goal of handling merge events. During this phase, moderators with highly overlapping communities communicate each other so that, when a community is fully contained into another one, the smaller one can be absorbed (merged). When two communities have to be merged, the moderator of the smaller community destroys the community it is managing and deletes the relative entry in the DHT. No further action is needed because all the nodes inside the smaller community are also part of the larger one, so they have a reference to at least a moderator.

Experimental results: a Facebook case study

In this section we present an evaluation of SONIC-MAN by using a Facebook dataset. The evaluation was performed by simulations using PeerSim [START_REF] Montresor | PeerSim: A scalable P2P simulator[END_REF], an extremely scalable simulation environment that supports dynamic scenarios such as churn and other failure models.

The dataset

The dataset we used for our experiments contains information from real Facebook users gathered by a Facebook application, SocialCircles!1 . The application was deployed in 2014 and has gone under maintenance on the 1 st of May 2015 due to the change of the Facebook APIs which were substantially reduced in size. As described in [START_REF] De Salve | The impact of user's availability on On-line Ego Networks[END_REF], SocialCircles! was able to retrieve information about the topology and profile of registered users, and the online behaviour of them and their friends. The dataset is composed by 240 users monitored and their complete ego networks (for a total of 78,129 users). For each of the registered users we were able to gather their profile and ego network, and the interactions between them and the alters. Moreover, we also obtained temporal information about the total 78,129 users for 32 consecutive days. In detail, we sampled all the registered users and their friends every 5 minutes, for 32 days (from the 9 th March 2015 to the 10 th April of the same year).

An analysis of temporal information

Since the time aspect is the cornerstone of our research, we preliminary analysed the temporal information contained in our dataset. This preliminary analysis is aimed to understand a general trend of online/offline behaviour of the users.

We start by recalling that, in our dataset, time is modeled in a discrete way to represent the online/offline status of the users. In particular, each day of the monitored period consists of a finite number of time slots (i.e., 288 time slots each of 5 minutes), for a total number of 9251 time slots in the whole monitored period. For the sake of our analysis, by considering that a Facebook user can have three different status values (active, idle, and offline), we do not make any distinction if the user is active or idle, because in both cases the user is online, and his device can still help the network in delivering the service.

Online users A first interesting analysis, is to show which are the time spans during which the OSN is more crowded, by simply counting the online users at each time slot. In figure 2 we put the sorted time slots on the x-axis and on the y-axis we report the number of online users for each time slot. The Figure shows that there is a clear periodic pattern which reflects the day/night cycle. The repeated pattern shows two peaks and one nadir. By taking a closer look at the timestamps of the corresponding time slots, we can notice that the first peak is always registered around 12 PM (midday), the second one is registered around 9 PM and the nadir is registered around 6 AM. This observation confirms that users tends to follow a cyclic pattern of accesses to the service which may be guided by life duties and habits. By analyzing the amount of users online for each time slot, we can see that we have at most around 18,000 online users, roughly 23% of the total amount, and at least 3000, 3.8% of the total amount of users. Fig. 2: Online users count during the observed period Fig. 3: CDF of the number of sessions for each user in the observed period of time Online sessions A second analysis is to show for how long users remain online once logged in and how soon they come back online after going offline. To this aim we computed three measures: the session number, the session length, and the session inter-arrival time. A session is defined as the amount of time continuously spent on the OSN by a user.

The session number is the total amount of sessions of all the users. Figure 3 shows the Cumulative Distribution Function (CDF) of the number of sessions. As we can see most of the users has an high number of sessions during the whole observed period of time. More in detail, we can see that half of the users have more than 175 sessions and that only 20% of the users have 50 or less sessions. It is worthwhile to notice the presence of a very small fraction of inactive users, which had no sessions over the observed period of time.

The session length is the duration of a session of a user. It is important to point out that, since the time in our dataset is represented in a discrete way (time slots), each time we observe an online user in a particular time slot, we assume that the user was online during all the duration of that time slot. Figure 4a shows the CDF of the length of all the sessions. The plot shows that the majority of the sessions are very short with respect to the whole observer period. To better show the arrangement, we decided to make another plot to zoom on the leftmost part of the CDF. Figure 4b shows the CDF of the length of all the sessions, restricting to lengths ranging from 0 to 100 slots. As we can see from this figure, more than 80% of the sessions are shorter than 10 slots (50 minutes) and half of the sessions are, at most, 3 slots long. The session inter-arrival time measures the amount of time passing between two sessions of the same user, i.e. how much time a user spends offline. Figure 5a shows the CDF of the session inter-arrival time, and we can see that it is highly left skewed. Again, to better show the arrangement of the inter-arrival times, we decided to make a plot zooming on the leftmost part. Figure 5b shows the CDF of the length of all the sessions, restricting to lengths ranging from 0 to 100 slots. Session inter-arrival times tend to be slightly longer with respect to the session lengths, but are still very short.

These analyses showed that, as expected, the network is highly dynamic, and that we must take into account the fact that users tend to connect and disconnect from the service quite often.

A study of dynamic communities

We tested SONIC-MAN to assess its capabilities in finding community structures in a dynamic network and then we compared the results with a similar, but centralized, approach: TILES [START_REF] Rossetti | Tiles: an online algorithm for community discovery in dynamic social networks[END_REF]. For the purposes of this paper, we consider TILES as a centralized oracle. The choice of the algorithm with whom we compare SONIC-MAN was driven by two reasons, the first one being the fact that TILES is also a Temporal Trade-off CD algorithm and the latter motivation is the fact that it shares with this implementation of SONIC-MAN almost the same definition of community.

First of all, we analyse how community events, listed in [START_REF] Guidi | Dynamic community analysis in decentralized online social networks[END_REF], are redefined considering the working method of SONIC-MAN. Community detection algorithms emit sets of communities that can be matched later. Indeed, the matching phase was only a guess of the exact evolution of communities. Instead, thanks to our Fig. 5: CDF of the session inter-arrival time approach, we know exactly which is the evolution of each community. Events can be precisely detected by monitoring how the joining and leaving of nodes affect the community itself. We redefined the events as in the following:

-Birth: we say that a community is born whenever a node without a community succeed in closing a triangle which includes the node itself; -Death: we say that a community is dead whenever, after a node leaves the community, there are no more triangles in the community; -Merge: we say that two or more communities merge into a single community if each of the merging community is a subset of the same community, which will be the single one surviving the merging; -Split: we say that a community splits into a set of communities if, after a node leaves the splitting community, there are two or more triangle components.

We are ignoring all the other events because they are less relevant in a distributed environment. Our evaluation concerns the output of the algorithms considering at first the communities and then the community events. The first result is the number and size of communities discovered by SONIC-MAN. Table 1 shows the minimum, maximum, mean and standard deviation of number, aggregated by ego network, and size of the communities of both SONIC-MAN and TILES. The results of the table clearly confirms that the network is completely shattered. For SONIC-MAN, a high value of the size of communities confirms that, even tough the average number of online users is low, there is still an underlying community structure. Instead, TILES detects fewer communities in each ego network which are bigger with respect to the ones discovered by SONIC-MAN. We can explain this difference considering the fact that our algorithm is decentralized in contrast with the centralized nature of TILES.

After analysing the general structure of the network, we investigate the community events listed above. To do so, we compute some statistical measures on the events identified: birth, death, merge, and split events, aggregated by time 2, show a strong predominance of birth events and a very low number of split and merge events. This result clearly confirms the strong dynamism of the nodes of the network: communities form and dissolve at a high rate, each time a node joins or leaves the network. Of great interest is, again, a comparison with the results obtained by TILES (Table 2). In this case we observe an overall tie between birth and death events which dominate, in number, merge and split events. So, up to this point, we can say that there is a real community structure, but it is very unstable and hard to detect.

To further investigate this situation we decide to plot the number of the events divided for each time slot. The arrangement of events is showed in Figure 6 for SONIC-MAN and in Figure 7 for TILES. Events from the first time slot have been removed to better visualize the graph, because it was in the first time slot that we registered the maximum number of birth and death events. Again, this clearly shows both the temporal pattern already observed in Figure 2, and the predominance of birth and death events with respect to merge and split events, as seen in table 2. Nonetheless, there are some differences between the two graphs. First of all, as expected, death events are a less then birth events in figure 6 with respect to figure 7. Another interesting fact is that the overall number of events detected by SONIC-MAN is lower for all the events. While this, at a first sight, seems to be a bad property of our protocol, it is instead consistent with the philosophy behind it. We recall that, rather than developing another data mining tool, as in TILES, our protocol was designed as support to the development of more sophisticated distributed application.

Conclusion and Future works

In this paper we propose SONIC-MAN, a new distributed algorithm for dynamic community detection and management. This algorithm is designed to be used in DOSNs when a notion of community over time is needed to manage data availability and information diffusion. Our algorithm follows a Temporal Trade-off approach to keep overheads as low as possible while not giving up to the community quality. Moreover the communities detected are consistent through all the network thanks to the usage of super-peers. We evaluated our approach, comparing it with the results obtained with a similar, but centralized approach. The results show that SONIC-MAN provided results comparable to the centralized approach.

In the future we will evaluate new approaches for selecting the moderators and we will define a strategy to replicate social content exploiting the communities detected by SONIC-MAN. Finally, we are going to develop a completely decentralized version of the algorithm which avoids the use of super-peers.

Fig. 1 :

 1 Fig. 1: On the left, an example of a network. Figure A shows the ego network of node 10 and figure B shows the ego network of node 8. It is worthwhile to notice that node 4 belongs to the ego network of both node 10 and node 8

Algorithm 1 : 5 if reply = true then 6 store

 156 Node joining the network as alter of e 1 procedure NodeJoin(Ego e) 2 moderators ← DHT.getM oderators(e); 3 for each moderator m ∈ moderators do 4 reply ← m.send(e, "I AM ON LIN E");

Algorithm 2 :Algorithm 3 :

 23 Creation of a new community in the ego network of e 1 procedure CommunityForm(Ego e) 2 while true do 3 for each neighbour n do 4 pong[n] ← n.ping(); Node joining the network as an ego 1 procedure EgoJoin(Ego e) 2 moderators ← DHT.getM oderators(e); 3 for each moderator m ∈ moderators do 4 reply ← m.send(e, "I AM ON LIN E"); 5 store(reply.community); 6 DHT.setM oderator(e, myself );

  Fig. 4: CDF of the length of all the sessions

  (a) Plot showing the CDF of all interarrival times (b) Zoom, showing only inter-arrivals whose length is ≤ 100

Fig. 6 :Fig. 7 :

 67 Fig. 6: Community events detected by our algorithm

Table 1 :

 1 Statistical measures on number and size of dynamic communities detected by SONIC-MAN and TILES

			SONIC-MAN			TILES
	Measure	Min	Max	Mean	Std. Dev.	Min	Max	Mean	Std. Dev.
	Number	0	48	7.6	4.8	0	74	4.0	4.1
	Size	3	903	13.9	23.5	3	336	7.6	9.5
			SONIC-MAN			TILES
	Event	Min	Max	Mean	Std. Dev.	Min	Max	Mean	Std. Dev.
	Split	0	30	5.3	4.3	0	8	0.2	0.8
	Merge	0	31	7.0	5.5	0	146	60	34.6
	Death	0	198	47.4	28.1	0	1659	551.5	289.3
	Birth	0	1198	214.7	71.8	0	2412	551.6	289.6

Table 2 :

 2 Statistical measures on community events detected by SONIC-MAN and TILES slot and ego network. The results obtained by SONIC-MAN, reported in table

https://www.facebook.com/SocialCircles-244719909045196/


Remi Delassus Qucit

Romain Giot
email: romain.giot@u-bordeaux.fr

CNNs Fusion for Building Detection in Aerial Images for the Building Detection Challenge

This paper presents our contribution to the DeepGlobe Building Detection Challenge. We enhanced the SpaceNet Challenge winning solution by proposing a new fusion strategy based on a deep combiner using segmentation both results of different CNN and input data to segment. Segmentation results for all cities have been significantly improved (between 1% improvement over the baseline for the smallest one to more than 7% for the largest one). The separation of adjacent buildings should be the next enhancement made to the solution.

Introduction

The DeepGlobe Building Detection Challenge [START_REF] Demir | Deepglobe 2018: A challenge to parse the earth through satellite images[END_REF] follows the second round of the SpaceNet Challenge 1 . It poses the challenge of automatically detecting buildings from satellite images Top competitors of the SpaceNet challenge have submitted their code which is now publicly available 2 . We thus studied the winning solution that consists in an ensemble of three U-Net [START_REF] Ronneberger | U-net: Convolutional networks for biomedical image segmentation[END_REF] based models whose segmentation results are averaged, further called the "baseline".

A model built by merging the prediction of multiple sub models, like this one, is called an ensemble model; it generally performs better than the best of the merged models [START_REF] Kittler | On combining classifiers[END_REF]. The most common merging strategy for image segmentation is an unweighted average of the predictions.

We propose to replace the original unweighted average 1 https://community.topcoder.com/tc?module= MatchDetails&rd=16892

2 https://github.com/SpaceNetChallenge/ BuildingDetectors_Round2 by another ensemble model that we a call a deep combiner. Its architecture is equivalent to the combined models (i.e, U-Net based) and works with a MUL input as well as predicted segmentations. This combiner improves the baseline from 1% in Vegas to 7.4% in Khartoum.

This paper is organized as follows. Section 2 presents previous works on building detection and fusion techniques. We see here the existing building extraction methods, existing work on models' output fusion for segmentation, and SpaceNet's winning solution presentation. Section 3 presents our deep combiner. Section 4 shows the results; the combiner enhance the segmentation and the detection of buildings. Section 5 concludes this work.

Previous work

We based our model on the winning solution of the SpaceNet challenge. it used an unweghted average based ensemble of 3 U-Net models to segment buildings from the 8 MUL channels of the input Image as well as Open-StreetMap data. The contours of the building are then extractedd from the segmentation by grouping together into one building all connected pixels.

Limitations of the baseline

Several limits of the baseline appear. Firstly, the models are trained to predict a mask, which is not optimal. When two buildings are too close to each other, the contours of the buildings cannot be extracted from the corresponding mask (Figure 3) and the two buildings are considered as one.

Secondly, the post-processing is close to non existent. For example, one could use an instance segmentation model [START_REF] Bai | Deep watershed transform for instance segmentation[END_REF] or a flooding algorithm [START_REF] Meyer | Color image segmentation[END_REF] to split adjacent buildings. Those adjacent buildings will be fused into one single building if a group of at least one pixel adjacent to both of them is classified as a group of building pixels. Another example of what can be done during the post processing phase is the smoothing of building edges. Because most of the time, buildings have regular shapes, we can use this knowledge to predict shapes closer to reality. CRF [START_REF] Krähenbühl | Efficient inference in fully connected crfs with gaussian edge potentials[END_REF] techniques have been used to smooth edges and enhance the resolution of segmentations. It could help sharpening polygons and separating them.

Thirdly, more recent architectures such as DeepLab [START_REF] Chen | Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs[END_REF] or PSPnet [START_REF] Zhao | Pyramid scene parsing network[END_REF] could be used to try to enhance the segmentation score. They outperform the U-Net architecture in Im-ageNet [START_REF] Russakovsky | ImageNet Large Scale Visual Recognition Challenge[END_REF] segmentation tasks. However, their strong performance comes from the ability to detect tiny objects as well as big ones, which may not be so useful in the building detection problem.

Finally, a simple unweighted average is often a good default choice, as it will reduce the variance of the result, but might not be the best fusion solution as it gives the same importance to all models regardless of their performance, and is subject to errors when one of the merged models is overconfident, or when a large proportion of the merged models is erroneous. This critical proportion is easily reached when only three models are merged.

This study focuses on this final limitation. We thus review the state of ensemble modeling applied to problems of image segmentation.

Ensemble modeling for image segmentation

Ju et al [START_REF] Ju | The relative performance of ensemble methods with deep convolutional neural networks for image classification[END_REF] show that unweighted average (used by Marmanis et al [START_REF] Marmanis | Semantic segmentation of aerial images with an ensemble of cnss[END_REF] on multiple instances of the same model architecture and by Kamnitsas et al [START_REF] Kamnitsas | Ensembles of multiple models and architectures for robust brain tumour segmentation[END_REF] on complementary architectures) is a fusion method that performs as good as, if not better than, other known methods. It is favorable for reducing variance among predictions, but suffers from overconfident models. Majority voting (used by Dolz et al [START_REF] Dolz | Deep cnn ensembles and suggestive annotations for infant brain mri segmentation[END_REF]) generally has a lower performance pixel wise, but can produce an uncertainty map, which can be used to focus the model training on uncertain areas [START_REF] Wang | Gated convolutional neural network for semantic segmentation in high-resolution images[END_REF], or to prevent uncertain pixel classifications [START_REF] Kampffmeyer | Semantic segmentation of small objects and modeling of uncertainty in urban remote sensing images using deep convolutional neural networks[END_REF] which could help differentiate buildings close to each other and lead to worthier performances in building detection.

Weighted average with learned weights is called by Ju et al [START_REF] Ju | The relative performance of ensemble methods with deep convolutional neural networks for image classification[END_REF] a super learner. It is a model that takes segmentation as an input and outputs a more advantageous one. The simplest one can be seen as 1 * 1 * m convolution where m is the number of models fusionned. In their study on the CIFAR10 [START_REF] Krizhevsky | Learning multiple layers of features from tiny images[END_REF] dataset, they show that it usually performs better than unweighted averages but does not investigate more complex super learners, such as the one studied here; super learners taking neighborhood into account, or deep super learners. They do not talk about non learned weights, such as weighs accordingly proportional to the models' performances [START_REF] Lahiri | Deep neural ensemble for retinal vessel segmentation in fundus images towards achieving label-free angiography[END_REF], but we can reasonably assume that those weights would be reached by learn methods if they happened to be optimal, simply by setting them as initial weights.

The success of residual networks [START_REF] He | Deep residual learning for image recognition[END_REF] shows that learning residual functions with reference to the layer inputs, instead of learning unreferenced functions can lead to better performance. Scaled up to the model instead of the layer, we study a model that will use the input image as well as the fused models' outputs to learn a better segmentation. This additional input puts our model outside of the super learner category. We will label as combiners those models dealing with combining the output of other models, with or without additional outputs.

Proposed combiner

We propose a deep learning approach to the fusion of segmentation: a U-net based deep combiner that combines the segmentations output of the combined models as well as the MUL channels of the input image.

Architecture

The Deep combiner approach aims to enhance the segmentation by letting the deep neural network compute complex features such as edge detection, distance to building pixels etc. Moreover, this combiner uses not only the three predicted segmentations, but also the original image as input. This image can be used by the combiner model to determine the residuals of input models and fix their mistakes. We use the MUL channels of the original image as input.

We use the same U-Net architecture as input networks, with 29 hidden layers and 7 838 273 parameters. This architecture is usually used to segment images. Combining segmentations into one can be seen as performing a new segmentation on an image in which some channels correspond to some proposed segmentations. It thus makes sense to use a segmentation architecture to perform the combination. This combiner was not manually initialized to perform the unweighted average of the previous segmentation as it would jeopardize the learning process. Weigths are initialized with a uniform distribution between -0.05 and +0.05. We name this combiner the U-net approach.

Training

Training data is augmented, as we don't have enough images for some cities to train a deep learning model. For example, we train the model for Khartoum on 708 images and validate it on 304. The additional data comes from the rotation of the original image of 90, 180 and 270 degrees, as well as a symmetry along both axis.

We train our combiner during 20 epochs with a batch size of 1. We selecte the best epoch based on the validation score. Optimal validation score is usually reached between We evaluate the segmentation using the Jaccard coefficient [START_REF] Jaccard | Distribution de la flore alpine dans le bassin des dranses et dans quelques régions voisines[END_REF] for our loss function. It is the closest metric to the IoU score (used to judge if two polygons match) when it comes to image comparison. Given a ground truth labeling y * and a predicted segmentation to be evaluated ŷ, the Jaccard coefficient is defined as:

J(y * , ŷ) = y * ∩ ŷ y * ∪ ŷ (1)
which for images translates into:

J(y * , ŷ) = (y * * ŷ) (y * + ŷ) -(y * * ŷ) (2)
With the assumption that J(0, 0) = 1. As the Jaccard coefficient produces a value between 0 and 1, it is straightforward to transform it into a loss function:

J l (y * , ŷ) = 1 -J(y * , ŷ) (3)
Experiments have been run on a Linux computer with the following characteristics: Intel(R) Core(TM) i7-6950X CPU @ 3.00GHz, three Titan X Pascal GPUs (used to train multiple model in parallel, with one model per GPU) and 120Gbits of RAM, using Keras

Results

F-score improvement

Table 1 reports the maximum value of F-score obtained on each city dataset with the baseline and the combiner. The gain is defined as Gain = (N ew Score -Baseline)/Baseline. There has only been a slight improvement on Vegas because the baseline is already performing extremely well. However a large improvement on Khartoum shows that our solution can address more cases than a simple unweighted average.

Visualization of Detected Buildings

Images in Figures 1 and2 have been produced with the SpaceNet Challenge Building Detector Visualizer3 . Ground truth and predicted polygons are overlaid over the RGB images. Matching ground truth and predicted polygons are white. Yellow polygons are false positives (predicted polygon with no matching ground truth). Blue polygons are false negatives (ground truth polygon with no matching prediction).

A vast majority of buildings are properly segmented. Only buidings with a surface area significantly smaller than surrounding buildings are ignored by the combiner. The major difficulty is to separate buildings too close from each other.

Discussion

We have been able to highlight two main sources of errors. The first one is the adjacent buildings problem (Fig- 2. Example of high building density images. We can see that a large majority of the buildings are correctly detected. The few errors come from the smaller buildings, or from small parts of buildings cut at the edges of the image, as well as adjacent buildings being merged into one. ure 3). When we reduce the model uncertainty around buildings, adjacent buildings are considered as one unique building instead of two different ones. The second one comes from numerous errors in labeled data. Those errors can prevent the models to learn useful features or can punish them when they do. Missing a lot of small buildings will have a huge impact on the F-score, but smaller buildings are not consistenly labeled, especially in Shanghai.

To solve the adjacent buildings problem, Marmanis et al [START_REF] Marmanis | Classification with an edge: improving semantic image segmentation with boundary detection[END_REF] introduce the border class, such that the model classifies each pixel in three classes: building, building border, and background. It is then easier to split adjacent buildings. Yuan et al [START_REF] Yuan | Learning building extraction in aerial scenes with convolutional networks[END_REF] use a distance field as label. Each pixel value is its distance to the closest border (negative when inside a building). It is then possible to configure the postprocessing and set a predicted distance (0 in the mask) as the border. But it requires a large receptive field for this dataset. We used the same architecture for the combiner as the one used for the combined models. More architectures should be tested to determine if regular convnets are the best combiners. Maggiori et al [START_REF] Maggiori | Recurrent neural networks to correct satellite image classification maps[END_REF] used a recurrent neural network to improve their segmentation, which is another solution. Bai et al [START_REF] Bai | Deep watershed transform for instance segmentation[END_REF] used a new architecture of convnets to perform an instance segmentation. Their model takes the input image and the result of a segmentation as an input, just like our U-net.

The deep combiner was only tested with the combined learned output segmentation and the MUL input. The OSM layers and multi band inputs were not used. Of the three combined learners, the best ones don't use RGB, but multiband image and OSM layers. A deep combiner using those inputs is likely to have better performances too and will thus be implemented once the adjacent buildings' problem will be solved.

Conclusion

This paper addresses the problem of segmenting buildings from aerial images. It proposes a fusion solution for an ensemble of U-net models used to segment aerial images and extract buildings' contours from the segmentation. We used SpaceNet's challenge winning solution as a baseline to evaluate the benefits of combiners over unweighted averages for model fusion. This baseline corresponds to an ensemble of three models with the same architecture but different inputs. For two of the three studied images set (Vegas and Khartoum), a better segmentation led to a better Fscore, and combiners were thus performing superiorly than the existing unweighted averages. For the Paris dataset, the enhancement of the segmentation led to a worsened F-score, showing that the separation of adjacent buildings should be the next part of the solution to enhance.

Future work will focus on adjacent buildings' separation, thanks to an advantageous label such as the addition of a building borders class, or through post processing of the segmentation, as proposed by Bai et al [START_REF] Bai | Deep watershed transform for instance segmentation[END_REF].

  [4] 1.2.2 with Tensorflow [1] 1.4.0.

Figure 1 .

 1 Figure 1. Example of errors. In the first image adjacent buildings are fused because they were too close from each other. In the second image only the big buildings have been detected while the little roofs have not.

Figure

  Figure2. Example of high building density images. We can see that a large majority of the buildings are correctly detected. The few errors come from the smaller buildings, or from small parts of buildings cut at the edges of the image, as well as adjacent buildings being merged into one.

F-score : 1 Figure 3 .

 13 Figure 3. Adjacent buildings problem. When two buildings are too close to each other, a perfect model will produce only one building if the chosen label is a mask.

Table 1 .

 1 F-score, of the baseline and U-Net combiners over the validation set (including U-Net gain over baseline) compared to U-Net combiner final score for this challenge.

	City	Baseline U-Net	U-Net final score
	Vegas	0.8559	0.8639	0.8057
		-	+0.93%
	Paris	0.6805	0.7080	0.6787
		-	+4.04%
	Shanghai	0.5627	0.5794	0.5661
		-	+2.97%
	Khartoum 0.5855	0.6290	0.6387
		-	+7.43%
	epoch 5 and epoch 10.

https://github.com/SpaceNetChallenge/ BuildingDetectorVisualizer


J J Moreau

New computation methods in granular dynamics

The dynamics of collections of bodies, treated as perfectly rigid, involves nonsmooth mathematical relations, arising from the unilaterality of impenetrability constraints, from the formulation of dry friction and from the velocity jumps produced by possible collisions. The presented numerical methods treat nonsmoothness without resorting to regularization procedures. The examples shown concern populations of balls contained is a vertically vibrated rectangular box. First, a comparison is made with some experiments pe1formed by other authors, about the paradoxical shape taken by the free surface when vibration is not strong enough to fluidize it. Other examples reveal an unexpected mechanism of size segregation.

INTRODUCTION

Numerical methods have been developed for a few years in our laboratory, devoted to compu ting the motion of mechanical systems with transient contacts. One is then in the presence of unilateral constraints : since some parts of the system may enter into contact or get loose from each other, but can never interpenetrate, the permitted configurations are characterized by inequalities (possibly an infinite set of them). In the configuration space, this defines a region with corners and edges, instead of the smooth submanifolds which, . in the traditional Analytical Dynamics, are associated with cons traints. In the case of contact, we take dry fric tion into account under its sirnplest phenomeno logical description, namely the law of Coulomb. The latter consists in a relationship between the sliding velocity and the contact force which as sumes different analytical forms, depending on the sliding status ; and this relationship does not permit to express any of the two vector va riables as a fonction of the other. Furthermore, if collisions occur, one should expect velocity jumps, so that the evolution cannot be governed as a whole by differential equations nor diffe rential inclusions in the classical sense. For ail these reasons, the investigated problems belong to Nonsmooth Mechanics, a domain for which theoretical and numerical methods have specifi cally been elaborated in recent years (Moreau, Panagiotopoulos andStrang 1988, Moreau andPanagiotopoulos 1988).

Traditionally, the numerical approach to nonsmoothness rests on smoothing procedures, i.e. the investigated problems are approximated by regular ones to which usual computation methods are applied. For instance, impenetra bility is replaced by a steep repulsion potential acting when the concerned bodies corne close to each other. This is similar to the "penalty me thods" used in Constrained Optimization. The drawback is that the need of precision leads to introduce very stiff repulsion laws, so the nu merical stability of the consequent integration procedures requires fine time-discretization and much computing power. Since the pioneering work of P. A. [START_REF] Cundall | A computer model for si mulating progressive large scale movements of blocky rock systems[END_REF], significant re sults have however been obtained in that way (most recently : Gallas, Herrmann andSokolowski 1992a,b, Y-h Taguchi 1992) .

In contrast, we have decided to face nons moothness without resorting to regularization procedures. This results in algorithms efficient enough to treat on a microcomputer the dyna-mies of rigid body collections involving, say, 1000 contacts. Exarnples presented in the forth coming have however been computed on larger workstations. A frontal program on Macintosh have been developed to prepare the data and to analyse the results ; in particular, this program can exploit the numerical files in creating suc cessions of bitmap images on a hard disk, to be displayed as movie-like animations. Cunent applications are not limited to granulate mate rials ; for instance, the dynarnical behaviour of pieces of stonework supported by quaking ground is also actively investigated.

Ail the above methods compute motions by solving the equations of Dynarnics. Their aim is to investigate phenomena on the sarne footing as experiments, preferably in interaction with them. This places them at a different epistemo logical level than Monte Carlo or Cellular Automata simulations, the purpose of which is to develop and test the consequences of a priori conceptions.

COLLISIONS

We restrict ourselves in this communication to the treatment of bodies as peifectly rigid. A common weakness of ail numerical simulations developed in that framework lies in the difficulty of getting precise phenomenological information about collisions. Possible bounces are ascribed to some non analyzed microscopie elasticity. The traditional restitution coefficient of Newton can be experimentally identified only in the special case of the normal impact of spherical bodies. Recall that, if this coefficient is less that 1, bounce exhibits energy loss. A widespread conception is that such a dissipation should be the result of viscosity or plasticity effects localized in the vicinity of the impact locus. Actually, even if the colliding bodies are made of a perfectly elastic material, some Joss of kinetic energy must be expected at the macroscopic level. In fact, dynamical dis turbances emanate from the impact and are li kely to propagate throughout the concerned bodies. The amplitude of such vibrations may be small enough for the bodies to be described as rigid at the chosen level of observation, while, in view of the velocities involved in the vibration, the latter may carry nonnegligible energy. After the end of the collision process, vibration should last for a ce1tain time before internai dissipation progressively converts its energy into heat. Similarly, if a part of the in vestigated system collides with some fixed ex ternal boundary, an amount of energy is liable to propagate into the surrounding world. If the externat boundary moves, the energetic balance becomes still more complicated and the system may receive energy from the surrounding world. This is the case of a collection of rigid grains contained in a shaked vessel.

Common observation, as well as the compu tations made in our laboratory with body de formations taken into account through the finite eleme. nt method, show that restitution greatly depends on the shape of the colliding bodies and on the impact location.

Newton's restitution hypothesis involves the impinging and bouncing velocities only through their normal components. In the case of the oblique collision of, say, spherical bodies, fric tion is expected to transfer angular momentum. However short the collision process is, friction in the contact zone may evolve in a complex way, exhibiting microepisodes of slip and stick. As early as 1880, Darboux (see also [START_REF] Pérès | Mécanique Générale[END_REF] applied to rigid body collisions a multiple scaling method : the very short duration of the contact interaction is pararnetrized through a microtime, say "t. In applying the equations of rigid dynamics to the collision process, one treats the velocities of the involved bodies as unknown fonctions of "t, while positions are considered as constant. Coulomb law is invo ked, so as to relate, for every "t, the contact force with the sliding velocity at the contact point. Here again, it is implicitely assumed that microdeformations are concentrated in the vici nity of the impact locus. In our opinion, the probable global microdeformation of the bodies limits the applicability of the approach.

Anyway, Newton's hypothesis proves inade quate as soon as several contacts are present at the time of a collision. This is demonstrated by the familiar example of the rocking of a slender rectangular block supported by a fixed horizon tal plane. For simplicity, assume the lower edge slightly concave, so that contact can only occur through the two lower corners. The left corner remains in contact for an episode during which the block rotates to the right, then the right corner collides. If at this time Newton's as somption was applied to the left contact, no ro cking could be found.

A numerical method must be able to treat Our computing policy rests on a synthetic formulation of contact which applies to colli sion instants as well as to episodes of persistent contact. After time-discretization, this formula tion generates algorithms which, at every time step, are ready to face possible collisions or frictional catastrophes.

FORMALIZA TION OF CONTACT LA WS

Let the generic position of the considered sys tem be labelled by generalized coordinates, say qe R 0 • The geometric effect of impenetrability constraints are expressed by inequalities of the form fa(t,q)�O, the subscript a ranging in practice through a finite set (the presence of t in such inequalities pertains to the confinement of some parts of the system by boundaries with prescribed motion). Inequality holds as equality when contact occurs at some point, say Ma, of physical space. The central object, in mathema tical formulations as well as in computation, is the velocity fonction t�u(t)e R 0 from which the motion t�q(t) can be retrieved through time-integration.

Since we are to face collisions, the fonction u should not be expected continuous. The most natural setting consists in assuming that it has bounded variation from the investigated time interval I to R 0 (for theoretical arguments sup porting this assumption, see [START_REF] Moreau | An expression of classical dynamics[END_REF]. Then, at every te I, the fonction is sure to pos sess a left-limit u-(t) and a right-limit u + Let us say that a contact law is complete if it involves the three following implications fa(t,q) < 0 ::::} '!{_a= O. fa(t,q) � 0::::} na. 'U � �o na.'U� > 0::::} '!{_a = O. If all possible contacts are governed by laws agreeing with this definition, one easily esta blishes (see the author's contribution in Moreau & Panagiotopoulos 1988: 1-82) that the calcula ted motion satisfies fa(t,q(t))�O for every a, . and every tE I, provided this is true at the initial instant to.

Assuming a complete contact law readily secures the implication which, in view of the definition of 'U�, becomes

In the event �:t:O, this allows one to identifie P a with Newton's restitution coefficient, but not for �=0 ; such is the key to a consistent treatment of collisions in the case of multiple contacts.

In view of this, we respectively caHpa and 'ta the normal and the tangential restitution co efficient of contact a.

Coulomb's law of dry friction may easily be progranuned in the form of a complete contact law. It will then be applied at every time-step of the algorithm, for every contact detected as ac tive in this time step. The problem of determi ning the corresponding values of the contact impulsions � and, consequently, an estimate value of the velocity fonction at the end of the interval, is solved by an iteration procedure. Uniqueness of solution is not guaranteed. The reader may refer to Jean & Moreau 1992 for more detail.

COMPARISON WITH EXPERIMENTS

The first occasion of comparing directly our computations with observations was provided by the experiments made by M. [START_REF] Raous | Experimental analysis of the rocking of a rigid block[END_REF] on the rocking of rectangular blocks supported by a horizontal table which performs sinusoïdal horizontal oscillation. Satisfactory agreement with the simulation is obtained in this case by taking the normal restitution coefficient equal to zero. This conclusion also agrees with the findings of A. Ageno and A. Sinopoli (1993) in experiments motivated by the dynamics of dry stone buildings (ancient Greek monuments) under earthquakes.

In the proper domain of granular dynarnics, the currently continued experiments of E. Clement, J. Duran and J. Rajchenbach (1992) permit well controlled comparison.

Initial state

Figure 1 A collection of spherical beads with the same diameter (usually 1.5 mm) is placed in a rectangular cell with two parallel vertical glass walls of slightly greater spacing, allowing one to observe two-dimensional granular motion. The cell is given a vertical sinusoïdal vibration with frequency in the range 10-30 hertz. Amplitude is adjusted in such a way that the maximal acceleration aw 2 little exceeds gravity (for instance l.lg to l.Sg). ln view of their uniform diameter, beads arrange themselves into a cristal-like hexagonal packing. For aluminium beads, whose normal restitution coefficient is estimated at 0.7, no fluidization occurs in the top layers. Because of surface oxidization, the friction coefficient between beads is as high a 0.8. The following phe nomenon is observed. The top of the pack, ini tially a horizontal straight line due to prepara tory shaking, progressively builds a heap. The process emanates from the two lateral bounda ries whose average effect appears to drag the contacting beads downward. If aro 2 has values of order 1.lg to 1.3g, this effect is localized in the two upper corners. Randomly in time, vor tices appear in these corners, heaving some fragments of the bead pack into small heaps. As they grow, these two lateral heaps eventually merge into a single one, with maximal height at center.

When aro 2 is made greater, the downward drag exerted by lateral walls extends lower. This is precisely what happens in our simulation presented on fig. 1, which corresponds to a col lection of 1650 beads with aro 2 =I.63g. The downward currents affecting the two lateral boundary layers attain. the cell bottom. Sorne beads are consequently forced into the bulk, ge nerating rectilinear dislocations and the upsurge of central fragments of the hexagonal packing.

SIZE SEGREGATION IN VIBRATED PARTICULATE MATERIAL

We have applied the same program to various examples of two-dimensional collections of cir cular objects with non uniform sizes, contained in a vertically shaked box. In all the examples shown below, the box motion is the same : f r e quency 20 hertz, aro 2 =2g. Contact between objects has friction 0.8, normal restitution 0.9, tangential restitution O. Contact of objects with walls has friction 0.8, normal restitution 0.6, tangential restitution O. Computation is aimed at exhibiting the upward segregation of larger ob jects immersed in a population with diameters uniformly distributed between 1.5 mm and 0.75 mm. Such a dispersion of sizes prevents the formation of a cristal-like packing but here again, due to the large value of aro 2 , the downward flow localized in boundary layers is very apparent. Figure 2 shows a single large immersed ob ject with diameter 5 mm. For each of the 500 objects in presence, the total displacement of its center over some time interval, covering 16 vi bration periods, is drawn as a st. raight line star ting from the center of the initial position. This clearly displays a circulatory flow of the whole population. The large object takes part in this flow, without any visible tendency to go up faster than its surroundings. Animations created by the program show it reach the fluidized top region and then drift to one of the upper cor ners where it remains indefinitely. Apparently, the boundary layer is too thin to recycle it down, while the rest of the population continues to take part in circulatory currents. The motion is also affected by random fluctuations of various scales.

For comparison, figure 3 shows the compu tation results when boundary f r iction is made equal to zero, ail other data keeping the same values as above. No current now appears along the vertical walls, no general convective flow affects the bulk and the large object stays at bottom.

The case of several large objects yields similar results.

On the other hand, one may make the box

wider while increasing the total number of ob jects proportionnally so as to obtain the same height of granulate material. If boundary f r ic tion is nonzero the same downward boundary currents as in the preceding are visible, but the upward convective flow induced in the rest of the box is naturally slower.

In view of such simulations, one may sus pect that some experiments made in the past, with a view to produce size segregation, ac tually consisted in non segregating upward con vection while the downward boundary currents acted as filters. Experimental evidences howe ver seem to exist of segregation occmTing in the bulk of a granulate material. We expect to attain situations of this sort by suitably adjusting the computation data.

CONCLUSION

The numerical methods presented above work in three-dimensional situations as well. They today appear sufficiently validated to be used in the exploration of granular dynamics, including some slow shearing motions of compact granu late materials, not presented here. In our view, their major utility lies in joint use with experi ments. The three parameters of the assumed contact laws, namely the f r iction coefficient and the two restitution coefficients, have to be ad justed so that the computed results match as well as possible some feasible measurements of the experimental set-up. Then computation al-lows one to estimate the values of experimen tally inaccessible quantities, which may be of great help for understanding phenomena.

  collisions in multicontact situations. A decisive test is provided by thy transmission of impulse across a row of contacting balls, a classical ex periment displayed in many scientific museums.Incidentally, it has long been recognized that, in mechanical systems involving dry fric tion, velocity jumps may also occur in the ab sence of collision as the result of a sort of lo clcing. Concerning such "frictional catastrophes" (impossible in the free dynamics of bodies as regular as homogeneous balls) one may refer to the author's contribution in Moreau & Panagiotopoulos 1988: 1-82.

  such a fonction, a R 0 -valued measure on the interval I is classically associa ted, called the differential measure or Stieltjes measure of u, possibly denoted by du. If u is discontinuous at some point t of I, the measure du possesses an atom at this point, namely the R 0 -valued Dirac measure whose value equals the jump u + (t)-u-(t). In contrast, on any subin terval throughout which u admits a (Lebesgue integrable) derivative u', one has du=u'dt, whith dt denoting the Lebesgue measure (for a systematic exposition of such mathematical technicalities, the reader may refer to the au thor's contribution in Moreau, Panagiotopoulos & Strang 1988: 1-74). The equations of dy namics may then be written as an equality of R 0 -valued measures on the interval 1. This readily generates integration schemes : on every interval, say (ti,ti+t), of the time-discretization, the measure equality is replaced by the equality of the corresponding integraïs. Then u(t i+l ) plays the role of u + and u(lj) the role of u-. In this formulation, forces and percussions are treated on the same footing : classical forces are the densities relative to dt of diffuse impulsions, while percussions arising from collisions appear through their actual values (or equivalently through their densities relative to some atomic base measures). At the heart of the problem lies the formulation of laws governing contact effects at any instant where some of the inequalities fa�O hold as equalities. The geometrical inspection of the parametrization (q) allows one to express the relative velocity 'UaE R 3 of the contacting bodies at point Ma as a q-dependent linear fonc tion of ue R 0 ; in the case of a velocity jump, the same expression applies to the left-and right-limits. Since one is in want of phenome nological relations representing the whole colli sion process approximately, it proves expedient to construct some formai velocity 'U� as a weighted mean of the left-and right-limits. We choose to apply different weight coefficients when treating normal and tangential compo nents, namely Clearly 'U� equals 'U a whenever the latter is continuous. By a contact law we mean a relation between 'll� and the corresponding contact force or percussion denoted by !f?..a. Let na denote the normal unit vector to the contacting bodies at point Ma, with such a direction that na. '7.. 1 0 >0 corresponds to separation. Strictly speaking, na makes sense only for fa=O ; by convention, its definition is extended to neighbouring configurations.

Figure 2

 2 Figure 2