Dimitris Fotakis
email: fotakis@cs.ntua.gr

Laurent Gourvès
email: laurent.gourves@dauphine.fr

On the Distortion of Single Winner Elections with Aligned Candidates JAAMAS Track of AAMAS 2023

Keywords: Distortion, Single Winner Election, Obnoxious Facility

We study the problem of selecting a single element from a set of candidates on which a group of agents has some spatial preferences. The exact distances between agent and candidate locations are unknown but we know how agents rank the candidates from the closest to the farthest. Whether it is desirable or undesirable, the winning candidate should either minimize or maximize its aggregate distance to the agents. The goal is to understand the optimal distortion, which evaluates how good an algorithm that determines the winner based only on the agent rankings performs against the optimal solution. We give a characterization of the distortion in the case of latent Euclidean distances such that the candidates are aligned, but the agent locations are not constrained. This setting generalizes the well-studied setting where both agents and candidates are located on the real line. Our bounds on the distortion are expressed with a parameter which relates, for every agent, the distance to her best candidate to the distance to any other alternative.

Context

The problem of electing a set of representatives is central in social choice theory. Some voters (a.k.a. agents) express their preferences over a set of candidates and one has to aggregate the voters' preferences to identify the winners (see e.g., [START_REF] Zwicker | Introduction to the theory of voting[END_REF]). In typical voting scenarios, the voters can only express ordinal preferences over the candidates, which are consistent and summarize their cardinal preferences.

In a recent stream of articles (see, for example, [START_REF] Anshelevich | Distortion in social choice problems: The first 15 years and beyond[END_REF] for a recent survey), researchers study problems where some agents have latent distances over a set of candidates but these distances are unknown. Nevertheless, each agent has reported a ranking of the candidates. Though these rankings are consistent with the latent distance function, we are not guaranteed to find the candidates whose aggregate distance to the agents is minimum, even if we aim to choose a single candidate [START_REF] Anshelevich | Randomized social choice functions under metric preferences[END_REF].

Similar to the approximation ratio [START_REF] Vazirani | Approximation algorithms[END_REF], the distortion measures the worst-case performance of an algorithm due to lack of cardinal information [START_REF] Procaccia | The distortion of cardinal preferences in voting[END_REF][START_REF] Boutilier | Optimal social choice functions: A utilitarian view[END_REF]. The intriguing question of determining the best distortion for selecting a single winner (called the metric distortion problem) has attracted a lot of attention [START_REF] Anshelevich | Approximating optimal social choice under metric preferences[END_REF][START_REF] Munagala | Improved metric distortion for deterministic social choice rules[END_REF][START_REF] Anshelevich | Approximating optimal social choice under metric preferences[END_REF]. Gkatzelis et al. [START_REF] Gkatzelis | Resolving the optimal metric distortion conjecture[END_REF] proposed a deterministic algorithm with distortion 3, which is optimal because no deterministic algorithm has distortion less than 3 [START_REF] Anshelevich | Approximating optimal social choice under metric preferences[END_REF][START_REF] Anshelevich | Approximating optimal social choice under metric preferences[END_REF]. Determining the best possible distortion for randomized algorithms is considered as a major open problem [START_REF] Anshelevich | Distortion in social choice problems: The first 15 years and beyond[END_REF]. Nevertheless, the special cases of 2 and 3 candidates are resolved [START_REF] Anshelevich | Randomized social choice functions under metric preferences[END_REF][START_REF] Kempe | An analysis framework for metric voting based on LP duality[END_REF][START_REF] Kempe | Communication, distortion, and randomness in metric voting[END_REF][START_REF] Charikar | Metric distortion bounds for randomized social choice[END_REF].

More insight into the problem can be gained when more information on the instance is available. In this respect, α-decisiveness, where α is a real in [0, 1], plays a key role [START_REF] Anshelevich | Randomized social choice functions under metric preferences[END_REF]. This parameter captures how much more the agents prefer their best candidate to any other alternative. In an α-decisive instance, every agent's distance to her closest candidate is at most the distance to her second closest candidate multiplied by α. Then, every agent is co-located with her top choice when α = 0. For the other extreme (α = 1), α-decisiveness does not constrain the agents' locations at all. The algorithm of Gkatzelis et al. has distortion 2 + α for α-decisive instances with at least 3 candidates [START_REF] Gkatzelis | Resolving the optimal metric distortion conjecture[END_REF]. The deterministic lower bound of 3, which relies on a two-candidate instance, can be extended to show that when the number of candidates m is at least 2, no deterministic algorithm has α-distortion less than 1 + 2α. The upper and lower bounds do not match anymore under the α-decisiveness framework, but Gkatzelis et al. proposed a lower bound which approaches 2 + α when the number of candidates m tends to infinity [START_REF] Gkatzelis | Resolving the optimal metric distortion conjecture[END_REF]. When m = 2, the deterministic algorithm which outputs the top choice of a majority of agents has distortion 1 + 2α [START_REF] Anshelevich | Randomized social choice functions under metric preferences[END_REF][START_REF] Gkatzelis | Resolving the optimal metric distortion conjecture[END_REF]. Regarding randomized algorithms parameterized by α, the best lower and upper bounds, for any number of candidates m, are 2 + α -2(1 -α)/m and 2 + α -2/m, respectively [START_REF] Gkatzelis | Resolving the optimal metric distortion conjecture[END_REF].

Besides α-decisiveness, the metric distortion problem has been studied in the well-known case where agents and candidates are located on a real number line. The locations are unknown but the agents rank the candidates from the closest to the farthest. The preferences induced by this setting (a.k.a. 1-Euclidean because the distances are Euclidean and there is only one dimension) possess nice properties (namely, singlepeakedness [START_REF] Black | On the rationale of group decision-making[END_REF] and single-crossingness [START_REF] Samuel Karlin | Total Positivity[END_REF][START_REF] Mirrlees | An exploration in the theory of optimal income taxation[END_REF]) which can be favorably exploited by an algorithm. Anshelevich and Postl proposed a randomized algorithm with an optimal distortion of 1 + α for α-decisive instances on a line [START_REF] Anshelevich | Randomized social choice functions under metric preferences[END_REF]. They exploit the possibility to efficiently identify a set of (at most) two candidates which are consecutive on the line and to which the optimum must belong. Regarding deterministic algorithms, the aforementioned lower bound of 1 + 2α deriving from the lower bound of 3, applies to the case where agents and candidates are on a line. On the contrary, the candidates are not aligned in the lower bound approaching 2 + α presented in [START_REF] Gkatzelis | Resolving the optimal metric distortion conjecture[END_REF].

Elections share similarities with k-median and facility location problems [START_REF] Byrka | An improved approximation for k -median and positive correlation in budgeted optimization[END_REF][START_REF] Drezner | Facility Location: Applications and Theory[END_REF][START_REF] Feldman | On voting and facility location[END_REF]. The goal is to choose a subset of candidate locations where desirable facilities (e.g., schools) can be built. The total distance to some given agent set has to be minimized, assuming that each agent is connected to the nearest facility. Sometimes, the candidate to be selected is undesirable (e.g., a garbage depot or a candidate to leave a group of people). In this case, one wants to select a candidate of maximum total distance to the agents (see [START_REF] Church | Review of obnoxious facilities location problems[END_REF] for a recent survey on obnoxious facility location). Obnoxious facility location problems have previously received attention from several viewpoints. In a "pure" optimization framework, one wants to choose the location of the facilities and the true distances are accessible (see e.g., [START_REF] Tamir | Obnoxious facility location on graphs[END_REF][START_REF] Hosseini | Obnoxious Facility Location[END_REF] and the references therein). In the field of algorithmic mechanism design, the agents may misreport their preferences over the set of candidates so as maximize their individual distance to the winner(s). The authors of [START_REF] Cheng | Strategy-proof approximation mechanisms for an obnoxious facility game on networks[END_REF][START_REF] Mei | Mechanism design for one-facility location game with obnoxious effects on a line[END_REF][START_REF] Mei | Approximation strategy-proof mechanisms for obnoxious facility location on a line[END_REF] pursue the goal of designing (group) strategyproof mechanisms3 with the best possible approximation ratio. Recently, Chen et al. [START_REF] Chen | Favorite-candidate voting for eliminating the least popular candidate in a metric space[END_REF] studied the distortion of algorithms in a setting where the location of the candidates is known but the location of every agent is private. 4 They resolved the deterministic case for which the best distortion is 3. For randomized algorithms, a general lower bound of 1.5 is given, together with upper bounds for well studied special cases. In particular, they proposed two randomized mechanisms for building a single facility on the real line. The first mechanism is strategyproof and its distortion is 2. The second mechanism is not strategyproof but its distortion is lower: 13/7.

Contribution

Interested readers can refer to [START_REF] Fotakis | On the distortion of single winner elections with aligned candidates[END_REF] for the full version of this article.

We consider the metric distortion problem in α-decisive instances. The distances between agent and candidate locations are unknown but every agent has reported a strict preference over the candidate set. The influence of α-decisiveness on the agents' locations is clear when α = 0 or α = 1, but no previous work precisely explains (to our best knowledge) how α-decisiveness rules the agents' locations when α ∈ (0, 1). Our first contribution is to fill this gap by showing that agents lie inside some spheres under Euclidean distances. This characterization is interesting on its own and we exploit it in the full version of this article [START_REF] Fotakis | On the distortion of single winner elections with aligned candidates[END_REF].

Our second contribution is the definition of a domain which generalizes the well-studied case where both agents and candidates are located on the real line (1-Euclidean). In this generalization called AC for "Aligned Candidates", the candidates are aligned but the agent locations are not constrained. As for the 1-Euclidean case, the distances in the AC setting are Euclidean. As an application of AC, one can think of a straight road that crosses a region. The agents can be located anywhere in the region but the candidates must be along the road. One can also interpret the AC domain from an electoral perspective: every candidate lies on a left right political axis while the voters' ideological positions are more complex and require more dimensions.

We demonstrate that, as for the 1-Euclidean domain and under the assumption that no agent is equidistant from two distinct candidates, preferences remain single-peaked and single-crossing under the AC domain. Hence, when one wants to select a desirable candidate to which the agents want to be as close as possible, the set of potential optima can be reduced to two contiguous candidates, as for the 1-Euclidean case [START_REF] Elkind | Recognizing 1-Euclidean preferences: An alternative approach[END_REF][START_REF] Anshelevich | Randomized social choice functions under metric preferences[END_REF]. Since the metric distortion problem is resolved when m = 2 by selecting the candidate supported by a majority of the agents [START_REF] Anshelevich | Randomized social choice functions under metric preferences[END_REF][START_REF] Gkatzelis | Resolving the optimal metric distortion conjecture[END_REF], we get a deterministic algorithm with distortion at most 1 + 2α for any number of aligned candidates. This is the best possible ratio because the aforementioned lower bound of 1 + 2α applies to the setting of aligned candidates.

Afterwards, we investigate the distortion of choosing a single undesirable candidate. The aim is to determine the candidate that maximizes the total distance to the agents. As opposed to the setting studied in [START_REF] Chen | Favorite-candidate voting for eliminating the least popular candidate in a metric space[END_REF], we do not assume that the location of the candidates are public. We generalize the notion of α-decisiveness to the case of selecting an undesirable candidate. Namely, an instance is ᾱ-decisive, for some ᾱ ∈ [0, 1], if every agent prefers her best candidate (now, this is the farthest one) at least 1/ᾱ times more than her second best (the second farthest). Though this definition reads similar to that of decisiveness for a desirable facility, ᾱ-decisiveness constrains the instances in a very different way. We obtain tight bounds on the distortion of undesirable single winner election by deterministic algorithms, as a function of ᾱ, in two cases. When there are only two candidates and the latent distance function d is a metric (d is not necessarily Euclidean), we show that the simple algorithm which outputs the candidate ranked last by a majority of agents has distortion 1 + 2ᾱ and this is the best possible ratio.

We finally consider the AC domain with any number of candidates. As for the case of selecting a desirable candidate, the set of possible optima of the undesirable case with aligned candidates reduces to (at most) two elements which can be efficiently identified from the preference profile. However, these possible optima are typically different. All our bounds on the distortion for selecting an undesirable alternative are tight and summarized in the following table when m > 2 (the distortion is 1 + 2ᾱ when m = 2).

ᾱ < 1 3 1 3 ≤ ᾱ ≤ √ 2 -1 √ 2 -1 < ᾱ 1 3 ᾱ-ᾱ2 2-3 ᾱ-ᾱ2 1 + 2 ᾱ
Regarding these bounds, note that 3 ᾱ-ᾱ2 2-3 ᾱ-ᾱ2 = 1 when ᾱ = 1/3, 3 ᾱ-ᾱ2 2-3 ᾱ-ᾱ2 = 1 + 2 ᾱ when ᾱ = √ 2 -1, and 3 ᾱ-ᾱ2 2-3 ᾱ-ᾱ2 < 1 + 2 ᾱ for all ᾱ ∈ [1/3, √ 2 -1). Since ᾱ ∈ [0, 1], the distortion is always below 3, which is consistent with the results of [START_REF] Chen | Favorite-candidate voting for eliminating the least popular candidate in a metric space[END_REF].

In conclusion, all our bounds on the distortion, for both selecting a desirable or undesirable candidate, are best possible and derive from the same simple algorithm: identify a set of two candidates containing the optimum and return the one that is supported by a majority of agents.

Laurent Gourvès is supported by Agence Nationale de la Recherche (ANR), project THEMIS ANR-20-CE23-0018.

There is no incentive for a single agent or a group of agents to misreport their true rankings.

In the present work, the location of the agents and the candidates are private.


Cyrille Bertelle

Antoine Dutot

Frédéric Guinand

Damien Olivier

Organization Detection Using Emergent Computing

Keywords: Organization, community, dynamic graph, dynamic network, ant algorithm

Organization is a central concept in systems. In this paper an ant algorithm for detecting organizations is presented. In a discrete-time context, at each time-step, an organization corresponds to a set of closely interacting entities in a system. This system is mapped to a graph where nodes represent entities and edges represent interrelations. Several colonies of ants compete, and inside each colony, ants collaborate in order to colonize the graph. Detected organizations emerge from the global behavior of the ants. The proposed approach is compared to other methods on a graph where the organizations are already known. It is then tested on two real world graphs studied in the related literature.

Introduction

System: "Organized whole, made of interdependent elements that can only be defined in relation to each other, according to their place in this whole" F. de Saussure [10].

Ferdinand de Saussure proposes an interesting definition of the term "system". He highlights the concept of organization, connecting it with the whole and the interdependency. In other words, interrelations between elements, events or individuals, as soon as they are stable or regular, become organization generators, creators, attractive and eventually stable on the long term. The organization then connects elements, events or individuals by interrelations so that they become components of a whole. It assumes the solidarity and robustness of these links, and ensures that the system will eventually be long lasting despite random perturbations. The organization, therefore: transforms, produces, ties and maintains. Edgard Morin in "La Méthode" [START_REF] Morin | La méthode -1 -La nature de la nature[END_REF] proposes indeed the neologism "organisaction" to highlight the active feature. Furthermore, this organization can be produced by the system itself, and so it can exhibit autoorganizational traits, that is the ability to "auto-create" itself by producing its own organisaction principles in a continuous way. Matura and Varela go deeper with the term "autopoiesis", that is the property of living systems to auto-produce themselves permanently, to create continuously and without interruption their own living conditions. Results of the organization and of the functioning of the autopoeitic living are the ones that produce its organization and operation. Autopoiesis, or contin-uous reorganization, is a category that can apply to the whole biologic order, and by extension to the human social order.

In the domain of Artificial Intelligence, Swarm Intelligence refers to the collective intelligence of insect societies as described by ethologists. It consits in the building of simple reactive artificial individuals societies. Such individuals are able to collectively produce a complex response despite the fact they only have a local vision and have a simple behavior. The process is intrinsically decentralized. Problem resolution is obtained from the interactions and the dynamics of the system: intelligence appears collectively. The global result of the system is therefore emergent, made of a succession of "reflex"like behaviors. Such systems are characterized by their adaptivity and their robustness. Indeed, due to the decentralized control, each agent, according to its own perceptions, reacts to changes in its environment and is able to continuously adapt to variations of it. Furthermore, the agent count, their interchangeability and the absence of any centralized control make such a system fault and failure tolerant. A system like this is able to change its behavior during execution to adapt to the environment evolution, and so take into account its dynamics.

Organization is therefore a central concept in systems. They are represented as eventually evolving graphs (dynamic graphs [START_REF] Bertelle | Dynamic placement using ants for objects based simulations[END_REF]) whose vertices are the elements and edges represent interactions.

In this paper a new detection method based on an emergent computation mechanism [START_REF] Forrest | Emergent Computation chapter Emergent computation: self-organizing, collective, and cooperative phenomena innatural and artificial computing networks[END_REF] implemented by an ant algorithm is presented. Using ant algorithm for emergent computing has been already successfully applied. In [START_REF] Lafourcade | Algorithme de fourmis pour le traitement de la langue naturelle[END_REF] such an approach is used for addressing the problem of Word Sense Disambiguation (WSD) in the domain of computational linguistics. The corresponding application graph is static. Vertices correspond to word meanings and the initial topology is given by the morphosyntactic tree of the analyzed sentence. During the resolution process, distinct colonies compete for imposing their meanings. They strike against colonies associated to opposite senses and collaborate with colonies associated to close meanings.

The same algorithm has been applied for addressing the dynamic load balancing problem [START_REF] Cardon | Competing Ants for Organization Detection: application to Dynamic Distribution[END_REF]. The target application is a simulation of an ecological Individual-Based Model (IBM). The vertices of the considered dynamic graph are biological entities (different species) as well as inorganic particles, and the edges represent the interactions between these entities.

The underlying organizations are groups of biological entities. Indeed, during the execution, entities self-organize themselves in groups according to different situations. As conditions change during the simulation, groups may appear or disappear in an unpredictable way. The idea was to use these groups as the basis for performing efficiently load balancing. The same method was also applied for building clusters of proteins from an homology graph. In such a static graph, vertices correspond to proteins and edges to closeness with respect to homology [START_REF] Bertelle | Protein homology graph colored with 6 colors[END_REF]. Based on some recent works [START_REF] Tranouez | Contribution à la modélisation et à la prise en compte informatique de niveaux de description multiples[END_REF][START_REF] Prevost | Modélisation multi-niveaux d'écosystème aquatique par des approches mixtes[END_REF], a method to interface the algorithm with other simulations taking into account both inorganic particles organization and biological entities organizations in order to detect specialized trophic chains is currently studied.

The rest of this paper is organized as follows: the next section presents other comparable methods for organization or community detection. Section 3. describes in detail the approach, the implemented method and proposes a model for it. Results that can be expected by the method are presented in section 4., and some perspectives are drawn in the conclusion.

State of the Art

Finding organizations in graphs has been studied recently [START_REF] Albert | Statistical mechanics of complex networks[END_REF][START_REF] Newman | The structure and function of complex networks[END_REF], but two domains have already worked in this direction:

• Graph partitioning;

• Hierarchical clustering. More recently, Girvan and Newman [START_REF] Girvan | Community structure in social and biological networks[END_REF] suggested an elegant global algorithm based on hierarchical clustering that extended the concept of vertex betweenness centrality of Freeman [START_REF] Freeman | A set of measures of centrality based upon betweenness[END_REF] also to edges. Newman also suggested a stochastic approaches, like the random walk [START_REF] Newman | Finding and evaluating community structure in networks[END_REF]. For a general review an discusion on the existing approaches see [START_REF] Danon | Comparing community structure identification[END_REF].

Graph Partitioning

Graph partitioning is a problem which appears in many different applications as VLSI design, data-mining, finite element and parallel computing, but the problem of finding organization can be considered.

Given a graph G = (V, E), where V is the set of vertex and E the set of edges that determines the connectivity between the nodes. Both vertex and edges can be weighted, where |v| is the weight of a vertex v, and |e| is the weight of edge e even if in most of the literature, they are given unit weights. The graph partitioning problem consists on dividing G into k disjoint partitions. The goal is to minimize the number of cuts in the edges of the partition, and on the other hand reduce the imbalance of the weight of the subdomains. The weight of a subdomain is the sum of the weights of the vertex allocated in it.

As this is an NP-complete problem [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF], for graphs with a large order it is not possible to guarantee the achievement of the best solution in a reasonable computation time: when the size of the graph increases, the execution time of an algorithm capable of solving the problem can be assumed to grow exponentially. Therefore the problem is practically unsolvable for most graphs and heuristic and probabilistic methods are considered to obtain solutions.

The methods presented below (2.1.1 and 2.1.2) use recursive bisection. First the graph is divided in two partitions, then each cluster is divided in two, and so on. This method needs log 2 (k) steps to divide the graph in k partitions.

Spectral Methods

A spectral method (i.e., methods using the eigenvalues and eigenvectors of a matrix representation of a graph) is based on the analysis of the adjacency matrix A = [a ij ] [START_REF] Fiedler | Algebraic connectivity of graphs[END_REF][START_REF] Donath | Lower bounds for partitioning of graphs[END_REF]. It consists to analyze properties of A. In particular, it is necessary to calculate the Laplacian matrix L = D -A and the normal matrix N = D -1 A where D is the diagonal degree matrix of vertices, if k ij is an element of the matrix D,

k ii = card(V ) k=1
a ik and a ik = 0 when i = k.

The smallest eigenvalue of L is 0, the second eigenvalue of the Laplacian matrix of a graph, λ 2 (L(G)), is the algebraic connectivity of graph G. Thus the vector v 2 corresponding to λ 2 (L(G)) is the eigenvector of algebraic connectivity, and has special properties. It is possible to divide the graph into two cluster with the minimal amount of connectivity between them with the following scheme:

If v 2 (n) < 0, place n in G 1 . If not, place n in G 2 .

Iterative Improvement

The Kernighan/Lin Algorithm [START_REF] Kernighan | An efficient heuristic procedure for partitioning of electrical circuits[END_REF] addresses the problem by providing a method to improve upon an initial allocation of nodes between two subgraphs. Thus the algorithm starts with balanced partition and exchanges vertices in each subgraph to improve cutsize. Till the cutsize is improved, the vertex pairs (one in each subgraph) which give the largest decrease in cutsize are exchanged. These vertices are locked. If no improvement is possible and some vertices are still unlocked, the vertices which give the smallest increase are exchanged. The algorithm by Fiduccia and Mattheyses [START_REF] Fiduccia | A linear time heuristic for improving network partitions[END_REF] improves this method, providing an extremely efficient linear-time technique.

Hierarchical Clustering

These methods are generally used to analyze data [START_REF] Everitt | Cluster Analysis[END_REF]. These are statistical methods for finding relatively homogeneous clusters of cases based on measured characteristics. The method starts with each case in a separate cluster and then combines the clusters sequentially, reducing the number of clusters at each step until only one cluster is left. When there are N cases, this involves N -1 clustering steps, or fusions. This hierarchical clustering process can be represented as a tree, or dendrogram and are generally based on an agglomeration algorithm.

This kind of methods can be used on graph. The main goal is to group the vertices in subsets which represent the organizations. A similarity measure d ij based on the graph structure is introduced between each pair of vertices. The algorithm begins with one organizations for one vertex, then in the following steps, the distance between each organizations is computed and the closest is merged.

Stochastic Approaches and Collective Explorations

Stochastic approach are generally based on random walk in graphs [START_REF] Newman | Finding and evaluating community structure in networks[END_REF] and its derivatives. A random walk is a simple stochastic process. It is a formalization of the intuitive idea of taking successive steps, each in a random direction. Thus if a simple random walk in an undirected graph G is considered, at each time step, if the walk is located at vertex u, it moves forward to a vertex v chosen uniformly at random from the neighbors of u. To detect organizations, the main idea lays on the fact that small random walks tend to be trapped into them [START_REF] Pons | Computing communities in large networks using random walks[END_REF][START_REF] Tadic | Exploring complex graphs by random walks[END_REF]. A dissimilarity index [START_REF] Zhou | Distance, dissimilarity index, and network community structure[END_REF] between two nearestneighboring vertices of the graph is measured by a random walk. It is used to determine if nearest-neighboring vertices must be in the same organization. It integrates both the local and the global structural information of the given graph and bias can be introduced.

Multi-agents system can be used to detect organizations, Young et al. [START_REF] Young | An agent-based algorithm for detecting community structure in networks[END_REF] proposed the following method : agents perform slightly biased walks on a graph and retain a list of the vertices they traverse. Based on this information, the agent then follow a simple voting routine whereby nodes are merged into organizations and excluded from others. After this process, a simple clean up scheme can be employed to deliver the desired number of organizations.

The Model

The goal is to find organizations inside a graph G = (V, E) representing entities V , and their interactions E. If interactions have various degrees of importance, edges can be weighted, this weight being noted |e| for the edge e. Organizations are informally defined in the graph G as: a set of entities more closely connected with each other than with the other parts of the graph. Note that this definition is very close to the various definitions of a community found in the literature. More closely connected means here that there can be more edges, but also that these edges may have stronger weights.

The Method

Several colonies of ants that travel inside the graph to detect organizations are used. As said above, ants are simple entities that collectively exhibit intelligent behavior. In our method collaboration between ants of a same colony allow to detect organizations, whereas competition between distinct colonies allows to separate organizations.

The algorithm used can be referred to as an ant algorithm, however it departs from the usual ACO (Ant Colony Optimization) as described in [START_REF] Dorigo | Ant Colony Optimization[END_REF] since it never globally evaluates solutions, that is, it does not use an objective function. In our algorithm, ants auto-organize themselves and produce solutions that can be observed in the graph, but these solutions are never retrofitted in the algorithm.

The ant algorithm use several colonies of ants, each of a distinct color. Ants travel inside the graph an lay down pheromones, information that can be detected by other ants. Pheromones are also colored. Ants tend to be repulsed by pheromones of other colors. Furthermore, in the case of a weighted graph, ants tend to favor edges with important weights.

The algorithm principle is to color organizations using pheromones. Each colony will collaborate to colonize zones, whereas colonies compete to maintain their own colored zone (see figure 1). Solutions will therefore emerge and be maintained by the ant behavior. The solutions will be the color of each vertex in the graph. Indeed, colored pheromones are deposited by ants on edges. The color of a vertex is obtained from the color having the largest proportion of pheromones on all incident edges.

The Ant

A colored dynamic graph G(t) = (E(t), V (t), C(t)) is de- fined such that: • V (t)
is the set of vertices at time t. Each vertex v is characterized by:

• a color c ∈ C(t),
• E(t) is the set of edges at time t. Each edge e is characterized by:

• a weight |e| ∈ N + that corresponds to interaction importance between the elements at each end of edge e. • a quantity of pheromones of each color.

• C(t) is a set of colors representing the ant colonies at time t.

¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¢ ¢ ¢ ¢ ¢ ¢ £ £ £ £ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¥ ¥ ¥ ¥ ¥ ¥ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ § § § § § § § § ¨¨¨¨¨© " " " " " " " " " " " " " " " " # # # # # # # # # # # # $ $ $ $ $ $ $ $ $ $ $ $ % % % % % % % % % % ' ' ' ' ' ' ' ' ' ' ' ' ( ( ( ( ( ( ( ( ( ) ) )
)

) )

)

) ) @ @ @ @ @ @ @ @ @ @ @ @ A A A The colored ants behavior is defined by algorithm 1. This algorithm is to be repeated iteratively for each ant. At each iteration the algorithm decides the node the ant will visit next. Two parameters are used T and A. A is a parameter that control competition among ants. When the proportion of pheromone having the same color as the ant compared to other colors is under A, the ant is in an hostile environment and flee to another zone of the graph chosen randomly. T is a stabilizing parameter avoiding that an ant flee all the time from node to node when they always fall in hostile environment. It allows them to better colonize zones. Usually, T = 2 and A is set to 1 on the number of colonies. Given this algorithm each colony competes to create colonized areas. As shown on figure 1, the same colony can occupy two or more distinct zones, and ideally it would be possible to use a small number of colonies to discover all the organizations in the graph. However it is also possible that two organizations side by side be colonized by the same colony. To avoid this issue, the algorithm starts with only two colonies (or more if it can be estimated that the graph necessarily contains more organizations) and introduces new colonies, keeping the ant population constant, until it is no more possible to add more.

0 0 0 0 0 0 1 1 1 1 1 1 2 2 2
A A A A A A A A A B B B B B B B B B B B B C C C C C C C C C C C C D D D D D D D D D D D D E E E E E E E E E E E E F F F F F F F F F G G G G G G H H H H H H
Q Q Q Q Q Q R R R R R R R R R R R R R R R R S S S S S S S S S S S S T T T T T T T T T T T T U U U U U U U U V V V V V V V V V W W W W W W X X X X X X X X X X X X X X X X Y Y Y Y Y Y Y Y Y Y Y Y ``````à
For each vertex of the graph a main color is computed and its proportion compared to other colors is determined (see figure 2). A vertex color is considered stable if it is larger than a given threshold ω. It is then possible to compute this proportion for all vertices of the graph and determine a global stability. This is this number that is used to know if it is possible to add more colonies or not. If the addition of another colony gives a stability that cannot reach ω, it is considered no more possible to add a colony. Usually, ω is set to 80%.

Results

In this section, a comparison of our algorithm results on a well known graph and then an exploration of graphs extracted from book databases is presented.

The Zachary Karate Club [START_REF]An information flow model for conflict and fission of small groups[END_REF] is a real world data set already studied for example in [START_REF] Newman | Fast algorithm for detecting community structure in networks[END_REF][START_REF] Newman | Finding and evaluating community structure in networks[END_REF][START_REF] Newman | Detecting community structure in networks[END_REF][START_REF] Bagrow | Local method for detecting communities[END_REF] that can be defined as a graph of 33 vertices. In these articles the authors propose several algorithms whose results are shown on figure 3(a). As it can be seen on figure 3(b), our algorithm matches exactly these results. In this representation, large circles drawn above edges represent the dominant pheromone color and the total pheromone intensity on the edge.

Browsing the Amazon.com book seller databases, it is possible, knowing the initial ISBN of a book to find all other books bought by customers at the same time. In the graphs shown on figure 4 and5, each vertex represents a book, and each edge represents a link "customers having bought this book also bought". Books suggested this way are almost always on similar topics. The graph obtained therefore contains areas on wide topics like "the web", "programming", "architecture", or "systems".

The figure 4 is extracted starting at one edition of "The art of computer programming, volume 1" [START_REF] Knuth | The Art of Computer Programming: volume 1, Fundamental Algorithms[END_REF]. The algorithm found 9 distinct partitions of different sizes. Two movies of larger graphs can also be downloaded in [START_REF] Bertelle | Graph extracted from the amazon.com databases, colored with 5 colors[END_REF][START_REF] Bertelle | Graph extracted from the amazon.com databases, colored with 8 colors[END_REF].

Our method was applied to a protein homology graph. In such a graph each vertex is a protein, and an edge exists between two proteins if they are considered close if they are functionally related. The graph has been taken from [START_REF] Adai | Lgl: creating a map of protein function with an algorithm for visualizing very large biological networks[END_REF]. You can see on the movie [START_REF] Bertelle | Protein homology graph colored with 6 colors[END_REF] an application of our method to such a graph, exhibiting cluster of similar proteins.

Discussion and conclusion

An ant algorithm using emergent computing to detect organizations in graphs representing numerous elements in interaction was presented in this paper. The ant algorithm use both Organizations are long lasting compared to their constituents. Identically the solutions proposed by the algorithm are maintained by the continuous exploration operated by ants. This implies that any change in the graph and therefore in the organization structure can be considered immediately, changing continuously the solution accordingly.

As vertices colors are given by the colored pheromone importance on all incident edges, it is possible to take into account several colors per edge (most prominent, second, third, etc.). This allows to detect areas where organizations overlap. Indeed organizations are not all completely distinct and such a feature could allow the detection of two closely related organi-zations where another method would only detect one.

The algorithm still presents some limitations. The major one is the number of colonies that must be fixed at the beginning and be less or equal to the number of organizations. Actually, to solve this problem the algorithm starts with a small number of colonies, and then introduces colonies one by one, while ω remains stable.

A method allowing to accelerate the solution emergent by adding weights to unweighted graphs using a graph layout is actually investigated. Graph layouts are geometrical descriptions of graphs that try to give a planar or tri-dimensional representation of the graph with the less edge intersection and node overlapping possible. Figures presented in this article use such a graph layout based on repulsive and attractive forces [START_REF] Eades | A heuristic for graph drawing[END_REF][START_REF] Seery | Designing network diagrams[END_REF]. As such force based layouts tend to push organizations (fol- lowing our definition, set of nodes more closely tied together than with others) one from another, tightly connected nodes are closer and loosely connected nodes are farther (see for example figure 4). It is thus possible to use edge length to add weights used by ants to discover organizations.

Although the algorithm presented here is only dedicated to organization detection, variations of it has been used to dynamically and adaptively distribute simulations made of large number of interacting entities [START_REF] Cardon | Competing Ants for Organization Detection: application to Dynamic Distribution[END_REF].

Fig. 1 .

 1 Fig. 1. Example of a colored dynamic graph.

Fig. 2 .

 2 Fig. 2. Example of a dynamic colored graph at five stages of its evolution with organization detection.

Fig. 3 .

 3 Fig. 3. Organizations in the Zachary Karate Club.

Fig. 4 .

 4 Fig.[START_REF] Bertelle | Graph extracted from the amazon.com databases, colored with 5 colors[END_REF]. Exploration of the Amazon.com databases starting from "The Art of Computer Programming" at 12 recursive levels.

Fig. 5 .

 5 Fig.5. Exploration of the Amazon.com databases starting from "The Ruby Way" at 20 recursive levels.

& & & & & & & & & & & &


Sami Hebib
email: hebib@laas.fr

Hervé Aubert
email: haubert@laas.fr

Olivier Pascal
email: opascal@cict.fr

Nelson J G Fonseca
email: nelson.fonseca@cnes.fr

Lionel Ries

Jean-Marc E Lopez

Reconfigurable pyramidal antenna loaded by a cut-off waveguide-application to ARNS/RNSS services

Keywords: Reconfigurability, dual-band antenna, circularly polarized fields, pyramidal geometry, radio navigation services

A novel reconfigurable and circularly polarized antenna topology for satellite application services, based on a pyramidal geometry, is proposed. Frequency agility is simply obtained by loading the radiating elements by Radio-Frequency switches. The ground plane of the antenna is perforated and loaded by a cut-off and open-ended waveguide. The length of this waveguide is adjusted to achieve a good trade-off between rear radiation and impedance matching. A specific application of this original topology is described in this paper. It consists in the design of a reconfigurable dual-band antenna for Aeronautical Radio Navigation Services (ARNS) and Radio Navigation Satellite Services (RNSS). The computed input return loss is lower than -10 dB in all the considered frequency bands and quasi-hemispheric radiation patterns are obtained. These results are in good agreement with the required Radio Navigation specifications.

I. INTRODUCTION

Multi-band or reconfigurable antennas are often considered on satellite systems to reduce the number of onboard or ground antennas, combining several applications on the same antenna. A design difficulty arises when frequency bands are too close for being considered as different bands but are also too distant to be easily matched on one single band of a multiband antenna. A typical example is provided by the design of a dual-band antenna that fulfills the frequency plan and technical specifications of the Aeronautical Radio Navigation Services (ARNS) and the Radio Navigation Satellite Services (RNSS) reported in Table I. As indicated in this Table, the ARNS combine E5a/L5, E5b and extended L1, while RNSS combine L2, E6 and extended L1: the E5 and E6 bands are too close for being considered as two different bands of the multiband antenna, but too distant to be easily matched on one operating band of the antenna (the required bandwidth would be around 13%). Since the extended L1 band is common to the satellite services, the idea exploited in this paper is to design an antenna that is able to switch between the E5 and E6 bands. The solution developed here is then a dual-band antenna, one of the two bands being switchable.

Few research works have been reported on dual-band reconfigurable antennas with one switchable band [START_REF] Behdad | Dual-Band reconfigurable antenna with wide tunability range[END_REF]2]. We propose here an original topology, based on pyramidal structures, loaded by cut-off and open-ended waveguide. The length of this waveguide is adjusted for achieving a good trade-off between rear radiation and impedance matching. Trap-loads are used to achieve multi-band operation while frequency agility is obtained by loading the radiating element by Radio-Frequency switches. This paper presents the design of a new version of the multi-band antenna recently reported by the authors in [START_REF] Hebib | Pyramidal multi-band antennas for GPS/Galileo/MicroSat applications[END_REF][START_REF] Hebib | Trap-loaded pyramidal tri-band antenna for satellite applications[END_REF]: this original version has frequency flexibility capability to match close operating frequency bands.

An application concerning the design of a reconfigurable dual-band antenna for ARNS and RNSS is described here. Electromagnetic simulation results are reported and confirm the antenna flexibility in terms of input matching. Simulated radiation patterns are also presented and are in a good agreement with required technical specifications. II. ANTENNA DESCRIPTION The proposed antenna is composed of four radiating elements placed symmetrically around an axis which is perpendicular to a perforated ground plane (Figure 1). In this figure, these elements are metallic wire monopoles but other types of radiating elements can be chosen (e.g., bow-tie planar antennas).

Fig. 1 The pyramidal antenna with monopoles as radiating elements and its perforated ground plane

The circular polarization is obtained when the monopoles are fed with a progressive 90° phase difference and equal amplitudes. The excitation points are located at the edge of the perforation and the monopoles form a non-zero inclination angle α with the ground plane. By varying this angle the antenna radiation pattern can be shaped to achieve various required specifications. As a matter of fact, tuning this angle allows bringing the excitation points more or less closer to each other and hence, the radiation pattern can be set either quasi-hemispheric or directive. The feeding ports are connected to the excitation points via 50Ω planar transmission lines. Each monopole contributes to the overall radiation patterns whatever the considered direction. A frequency transparent material (e.g., foam or polystyrene) may be placed under the substrate boards forming the pyramid in order to obtain a rigid radiating structure. The radius of the ground plane influences the antenna gain and axial ratio and it has to be chosen sufficiently large for limiting the reflection effect at the outer edge. Moreover, we have observed that the hole in the ground plane improves the matching at the excitation points. However, it generates an undesirable rear electromagnetic radiation. This rear radiation be reduced by loading the ground plane by a cut-off and open-ended metallic waveguide (see Figure 2). The metallic waveguide may be viewed as the continuity f the already existing o eated by the finite thickness of the ground plane together with the perforation. This waveguide is designed in such a way that no mode is propagating inside at the operating frequencies of the antenna (a lossless circular waveguide is considered cut-off when its radius is lower than the maximum allowed radius ensuring the evanescence of the first (fundamental) mode in the circular waveguide). The length of this waveguide has to be adjusted in order to achieve a good trade-off between rear radiation and the antenna matching.

In Figure 2 the dimensions l 1 , l 1 +l 2 and l 1 +l 2 +l 3 are approximately the lengths of quarter-wavelength monopo C. The use of trap-loads requires a minimum separation between two successive operating frequency bands. When two bands are too close and the bandwidth of the radiating elements are not wider enough to cover them simultaneously, it is preferable to use RF-switches instead of trap-loads. Due to their compactness, easy integration and reduced effect on the antenna radiation patterns, the chip components (capacitors and inductors) are very suitable for the practical realization of the trap-loads. However, the impedance matching and the bandwidth of the antenna are quite dependent on the performances of these chip components. Concerning the switches, RF Micro-ElectroMechanical switches can be used (examples of such integration in antennas may be found in [START_REF] Liu | A frequency-selectable patch antenna of circular polarization with integrated MEMS switches[END_REF][6][START_REF] Yang | Patch antenna with switchable slot (PASS): Dual frequency operation[END_REF]). Besides their compactness, these devices can outperform their semiconductor counterparts such as transistors and diodes in lower insertion loss [START_REF] Liu | A frequency-selectable patch antenna of circular polarization with integrated MEMS switches[END_REF]6], lower power consumption during operation and higher Q, which inherently fits the antenna requirements.

III. APPLICATION: RECONFIGURABLE DUAL-BAND ANTENNA FOR ARNS/RNSS SERVICES impedance dual-band cy plan and tec l while fine optimizations ha

The application considered here concerns the design of a antenna that fulfills the frequen hnical specifications summarized in Table I. Since the ARNS and the RNSS are sharing the same L1 band, the designed antenna is a dual-band antenna able to switch between E5 band and E6 band.

The first design of the antenna has been achieved by using IE3D electromagnetic simulation too ve been performed by means of CST Microwave Studio software. The resulting pyramidal antenna is shown in Fig. 2. The four radiating elements that constitute the antenna are metallic strips of width 1mm printed on a NELTEC substrate (ref. NY9208ST0762CTCT: relative permittivity of 2.08 and thickness of 0.762mm). The same substrate is used for the design of the 50Ω microstrip lines that place the four feeding ports at 20mm from the edge of the ground plane perforation. These 50Ω-microstrip lines have a width of w = 2.39mm and are printed on a 30mm x 30mm boards. The lengths l 1 , l 2 and l 3 (see Figure 2) are equal respectively to 35.7mm, 4.6mm and 1mm. The outer radius of the ground plane is 85mm. The cutoff and open-ended circular metallic waveguide, used for controlling the rear radiation and impedance matching, presents an inner radius equal to one of the ground plane hole (33mm) and a length h of 70mm. This length has been chosen to have a minimum of rear radiation and a good impedance matching at all operating frequencies. A pyramidal inclination of 45° is chosen as a good trade-off between the expected radial and axial radiation performances.

As above-discussed the agility between frequency bands 1 and 2 is achieved using RF-switches placed along the ra diating strips while the dual-band behavior of this antenna is obtained using trap-loads. The operating frequency bands and associated services versus the ON/OFF state of the RF-switches are reported in Table II. Once the strip dimensions defined, the trap-loads are replaced by i eal optimum parallel LC circuits (L=9.68nH and C=1.06pF). Consequently, the lengths of the strips need to be slightly adjusted accordingly for the lower bands. sults are in good agreement with the nominal required specifications. As expected the band 3 (extended L1) is available with the two ON/OFF switch states. Nevertheless, depending on the ON/OFF states either band 1 or 2 is selected. The return loss is lower than -10 dB over E5a/L5, E5b, E6 and extended L1. From the scattering parameters analysis, it appears that the impedance matching level in the lower bands is degraded, when compared to the band 3, due to electromagnetic coupling effects between the quarterwavelength monopoles (between two adjacent monopoles the coupling level at lower bands is found to be around -6 dB). This coupling may be reduced by modifying the monopole inclination angles.

Figure 4 shows the simulated Right Handed (RH-) and Left Handed (LH-) Circ the antenna at the three operating center frequencies (1.189GHz, 1.280GHz and 1.575GHz) for φ =0° and φ =45°. As it can be observed from this figure, the radiation patterns of the antenna are quasi-hemispheric at all operating frequencies, allowing a maximum reception of signals from the satellites in sight.

Fig. 2

 2 Fig. 2 Reconfigurable pyramidal antenna loaded by a cut-off and open-ended metallic circular waveguide

  Perforated ground erating at the three desired frequencies. Trap-loads and Radio-Frequency (RF) switches are inserted on the surface of the radiating elements to achieve the multiband behavior, frequency reconfigurability or the combination of the two. For a first rapid design the trap-loads are assumed to be perfect short-or open-circuits, depending on the frequency. Next, in order to perform an accurate design, trap-loads are modeled by a LC parallel circuit. At its resonant frequency ) 2 /( 1 LC π , the trap-load is equivalent to an open circuit; at lower frequencies, the trap-load presents low reactive that can be compensated by a slight change in the length of the radiating elements. The desired rejection frequency and bandwidth allow deriving the pertinent values of L and

Fig. 3 Fig. 4

 34 Fig. 3 Simulated return loss (in dB) when : (a) the switch is ON and (b) the switch is OFF. ( ) Nom equired specifications

TABLE II FREQUENCY

 II BAND SELECTION VERSUS SW