Tag Archives: ego-centered

Papers

Multi-ego-centred communities

Maximilien Danisch, Jean-Loup Guillaume and Bénédicte Le Grand

The community structure of a graph is defined in various ways in the literature:

  • partition, where nodes can belong to only one community. This vision is unrealistic and may lead to poor results because most nodes belong to several communities in real-world networks;
  • overlapping community structure, which is the most natural view, but is often very difficult to identify in practice due to the complex structure of real-world networks and the huge potential number of such communities;
  • egocentered community structure which focuses on individual nodes' communities and seems to be a good compromise.

In this chapter, the third vision is investigated; a new proximity measure based on opinion dynamics is proposed to score and select nodes according to their proximity to a node of interest. We call it the carryover opinion. In addition to be parameter-free, the carryover opinion can be calculated in a very time-efficient way and can thus be used in very large graphs.
We also go further in the idea of egocentered communities by introducing the new concept of multi-egocentered communities, i.e., focusing on the communities of a set of nodes rather than of a single node.
A key idea is that, although one node generally belongs to numerous communities, e.g., friends, colleagues, family, a small set of appropriate nodes can fully characterize a single community. We also show how to unfold all egocentered communities of a given node using this notion of multi-egocentered community.

Posted in Papers | Also tagged , |
Papers

Multi-ego-centered communities in practice

Maximilien Danisch, Jean-Loup Guillaume and Bénédicte Le Grand

We propose here a framework to unfold the ego-centered community structure of a given node in a network. The framework is not based on the optimization of a quality function, but on the study of the irregularity of the decrease of a proximity measure. It is a practical use of the notion of multi-ego-centered community and we validate the pertinence of the approach on benchmarks and a real-world network of wikipedia pages.

Posted in Papers | Also tagged , |
Papers

Towards realistic modeling of IP-level routing topology dynamics

Clémence Magnien, Amélie Medem, Sergey Kirgizov, Fabien Tarissan

Many works have studied the Internet topology, but few have investigated the question of how it evolves over time. This paper focuses on the Internet routing IP-level topology and proposes a first step towards realistic modeling of its dynamics. We study periodic measurements of routing trees from a single monitor to a fixed destination set and identify invariant properties of its dynamics. Based on those observations, we then propose a model for the underlying mechanisms of the topology dynamics. Our model remains simple as it only incorporates load-balancing phenomena and routing changes. By extensive simulations,  we show that, despite its simplicity, this model effectively captures the observed behaviors, thus providing key insights of relevant mechanisms governing the Internet routing dynamics. Besides, by confronting simulations over different kinds of topology, we also provide insights of which structural properties play a key role to explain the properties of the observed dynamics, which therefore strengthens the relevance of our model.

Posted in Papers | Also tagged , , |