One of the most useful measures of cluster quality is the modularity of the partition, which measures the difference between the number of the edges joining vertices from the same cluster and the expected number of such edges in a random graph. In this paper, we show that the problem of finding a partition maximizing the modularity of a given graph G can be reduced to a minimum weighted cut (MWC) problem on a complete graph with the same vertices as G. We then show that the resulting minimum cut problem can be efficiently solved by adapting existing graph partitioning techniques. Our algorithm finds clusterings of a comparable quality and is much faster than the existing clustering algorithms.

Designing an overlay network for publish/subscribe communication in a system where nodes may subscribe to many different topics of interest is of fundamental importance. For scalability and efficiency, it is important to keep the degree of the nodes in the publish/subscribe system low. It is only natural then to formalize the following problem: Given a collection of nodes and their topic subscriptions, connect the nodes into a graph that has least possible maximum degree in such a way that for each topict, the graph induced by the nodes interested intis connected. We present the first polynomial-time logarithmic approximation algorithm for this problem and prove an almost tight lower bound on the approximation ratio. Our experimental results show that our algorithm drastically improves the maximum degree of publish/subscribe overlay systems. We also propose a variation of the problem by enforcing that each topic-connected overlay network be of constant diameter while keeping the average degree low. We present three heuristics for this problem that guarantee that each topic-connected overlay network will be of diameter 2 and that aim at keeping the overall average node degree low. Our experimental results validate our algorithms, showing that our algorithms are able to achieve very low diameter without increasing the average degree by much.

Publish/subscribe communication systems where nodes subscribe to many different topics of interest are becoming increasingly more common. Designing overlay networks that connect the nodes subscribed to each distinct topic is hence a fundamental problem in these systems. For scalability and efficiency, it is important to keep the degree of the nodes in the publish/subscribe system low. Ideally one would like to be able not only to keep the average degree of the nodes low, but also to ensure that all nodes have equally the same degree, giving rise to the following problem: Given a collection of nodes and their topic subscriptions, connect the nodes into a graph with low average and maximum degree such that for each topic t, the graph induced by the nodes interested in t is connected. We present the first polynomial time parameterized sub linear approximation algorithm for this problem. We also propose two heuristics for constructing topic connected networks with low average degree and constant diameter and validate our results through simulations. In fact, the results in this section are a refinement of the preliminary results by Onus and Richa in INFOCOM'09.

Designing an overlay network for publish/subscribe communication in a system where nodes may subscribe to many different topics of interest is of fundamental importance. For scalability and efficiency, it is important to keep the degree of the nodes in the publish/subscribe system low. It is only natural then to formalize the following problem: Given a collection of nodes and their topic subscriptions connect the nodes into a graph which has least possible maximum degree and in such a way that for each topic t, the graph induced by the nodes interested in t is connected. We present the first polynomial time logarithmic approximation algorithm for this problem and prove an almost tight lower bound on the approximation ratio. Our experimental results show that our algorithm drastically improves the maximum degree of publish/subscribe overlay systems. We also propose a variation of the problem by enforcing that each topic-connected overlay network be of constant diameter, while keeping the average degree low. We present a heuristic for this problem which guarantees that each topic-connected overlay network will be of diameter 2 and which aims at keeping the overall average node degree low. Our experimental results validate our algorithm showing that our algorithm is able to achieve very low diameter without increasing the average degree by much.

Designing an overlay network for publish/subscribe communication in a system where nodes may subscribe to many different topics of interest is of fundamental importance. For scalability and efficiency, it is important to keep the degree of the nodes in the publish/subscribe system low. It is only natural then to formalize the following problem: Given a collection of nodes and their topic subscriptions connect the nodes into a graph which has low average and maximum degree and in such a way that for each topic t, the graph induced by the nodes interested in t is connected. We present the first polynomial time parameterized sublinear approximation algorithm for this problem.

We consider the problem of designing a distributed algorithm that, given an arbitrary connected graph G of nodes with unique labels, converts G into a sorted list of nodes. This algorithm should be as simple as possible and, for scalability, should guarantee a polylogarithmic runtime as well as at most a polylogarithmic increase in the degree of each node during its execution. Furthermore, it should be self-stabilizing, that is, it should be able to eventually construct a sorted list from any state in which the graph is connected. It turns out that satisfying all of these demands at the same time is not easy. Our basic approach towards this goal is the so-called linearization technique: each node v repeatedly does the following with its neighbors: for its left (i.e., smaller) neighbors u1, …, uk in the order of decreasing labels, v replaces {v, u1}, …, {v, uk} by {v, u1}, {u1,u2},…, {uk − 1,uk}, and for its right (i.e., larger) neighbors w1, …, wℓ in the order of increasing labels, v replaces {v, w1}, …, {v, wℓ} by {v, w1}, {w1, w2}, …, {wℓ − 1, wℓ}. As shown in this paper, this technique transforms any connected graph into a sorted list, but there are graphs for which this can take a long time. Hence, we propose several extensions of the linearization technique and experimentally evaluate their performance. Our results indicate that some of these have a polylogarithmic performance, so there is hope that there are distributed algorithms that can achieve all of our goals above.

We consider the well-known vertex coloring problem: given a graph G, find a coloring of the vertices so that no two neighbors in G have the same color. It is trivial to see that every graph of maximum degree Delta can be colored with Delta + 1 colors, and distributed algorithms that find a (Delta + 1)-coloring in a logarithmic number of communication rounds, with high probability, are known since more than a decade. This is in general the best possible if only a constant number of bits can be sent along every edge in each round. In fact, we show that for the n-node cycle the bit complexity of the coloring problem is Omega(log n). More precisely, if only one bit can be sent along each edge in a round, then every distributed coloring algorithm (i.e., algorithms in which every node has the same initial state and initially only knows its own edges) needs at least Omega(log n) rounds, with high probability, to color the cycle, for any finite number of colors. But what if the edges have orientations, i.e., the end-points of an edge agree on its orientation (while bits may still flow in both directions)? Does this allow one to provide faster coloring algorithms? Interestingly, for the cycle in which all edges have the same orientation, we show that a simple randomized algorithm can achieve a 3-coloring with only O(radic(log n)) rounds of bit transmissions, with high probability (w.h.p.). This result is tight because we also show that the bit complexity of coloring an oriented cycle is Omega(radic(log n)), with high probability, no matter how many colors are allowed. The 3-coloring algorithm can be easily extended to provide a (Delta + 1)-coloring for all graphs of maximum degree Delta in O(radic(log n)) rounds of bit transmissions, w.h.p., if Delta is a constant, the edges are oriented, and the graph does not contain an oriented cycle of length less than radic(log n). Using more complex algorithms, we show how to obtain an O(Delta)-coloring for arbitrary oriented graphs of maximum degree Delta using essentially O(log Deltaradic(log n)) rounds of bit transmissions, w.h.p., provided that the graph does not contain an oriented cycle of length less than radic(log n)

An important problem for wireless ad hoc networks has been to design overlay networks that allow time- and energy-efficient routing. Many local-control strategies for maintaining such overlay networks have already been suggested, but most of them are based on an oversimplified wireless communication model. In this paper, we suggest a model that is much more general than previous models. It allows the path loss of transmissions to significantly deviate from the idealistic unit disk model and does not even require the path loss to form a metric. Also, our model is apparently the first proposed for algorithm design that does not only model transmission and interference issues but also aims at providing a realistic model for physical carrier sensing. Physical carrier sensing is needed so that our protocols do not require any prior information (not even an estimate on the number of nodes) about the