**Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?**

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Concept# Community structure

Résumé

In the study of complex networks, a network is said to have community structure if the nodes of the network can be easily grouped into (potentially overlapping) sets of nodes such that each set of nodes is densely connected internally. In the particular case of non-overlapping community finding, this implies that the network divides naturally into groups of nodes with dense connections internally and sparser connections between groups. But overlapping communities are also allowed. The more general definition is based on the principle that pairs of nodes are more likely to be connected if they are both members of the same community(ies), and less likely to be connected if they do not share communities. A related but different problem is community search, where the goal is to find a community that a certain vertex belongs to.
Properties
In the study of networks, such as computer and information networks, social networks and biological networks, a number of different characte

Source officielle

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés

Chargement

Cours associés

Chargement

Séances de cours associées

Chargement

Publications associées (12)

Unités associées

Aucun résultat

Chargement

Chargement

Chargement

Personnes associées

Aucun résultat

Concepts associés (6)

Théorie des réseaux

vignette|Graphe partiel de l'internet, basé sur les données de opte.org du 15 janvier 2005 (voir description de l'image pour plus de détails)
La théorie des réseaux est l'étude de graphes en tant que

Science des réseaux

vignette|Les liens de la network science
La Science des Réseaux, ou Network Science, est une discipline scientifique émergente qui se donne pour objet l'étude des relations, liens et interconnexions e

Réseau complexe

En théorie des graphes, un réseau complexe est un réseau possédant une architecture et une topologie complexe et irrégulière. Comme tous les réseaux, ils sont composés de nœuds (ou sommets ou points)

Cours associés (9)

ENV-220: Fundamentals in ecology

The students will learn the fundamentals in ecology with the goal to perceive the environment beyond its physical and chemical characteristics. Starting from basic concepts, they will acquire mechanistic understanding of biodiversity, ecosystem functioning and global change.

CS-423: Distributed information systems

This course introduces the key concepts and algorithms from the areas of information retrieval, data mining and knowledge bases, which constitute the foundations of today's Web-based distributed information systems.

COM-308: Internet analytics

Internet analytics is the collection, modeling, and analysis of user data in large-scale online services, such as social networking, e-commerce, search, and advertisement. This class explores a number of the key functions of such online services that have become ubiquitous over the past decade.

Séances de cours associées (17)

Mireille El Gheche, Zahra Farsijani, Pascal Frossard, Matthias Minder

In many applications, a dataset can be considered as a set of observed signals that live on an unknown underlying graph structure. Some of these signals may be seen as white noise that has been filtered on the graph topology by a graph filter. Hence, the knowledge of the filter and the graph provides valuable information about the underlying data generation process and the complex interactions that arise in the dataset. We hence introduce a novel graph signal processing framework for jointly learning the graph and its generating filter from signal observations. We cast a new optimisation problem that minimises the Wasserstein distance between the distribution of the signal observations and the filtered signal distribution model. Our proposed method outperforms state-of-the-art graph learning frameworks on synthetic data. We then apply our method to a temperature anomaly dataset, and further show how this framework can be used to infer missing values if only very little information is available.

Community structure in graph-modeled data appears in a range of disciplines that comprise network science. Its importance relies on the influence it bears on other properties of graphs such as resilience, or prediction of missing connections. Nevertheless, research to date seems to overlook its effect on the properties of signals defined in the domain of graphs' vertices. Indeed, the framework of graph signal processing mainly focuses on local connectivity patterns reflected by the graph Laplacian, and the Laplacian's effect on signals as the graph equivalent of a differential operator. This dissertation investigates the aforementioned interplay between graph signals and the underlying community structure. We make an effort to answer questions like -- do signal's values align and in what way with the communities?; does localization of signal's energy favors a community as the vertex support? Answers to these questions should provide a clearer perspective on the relation between graph signals and networks at the level of subgraphs.This dissertation consists of two main parts. First, we investigate a particular approach -- based on modularity matrix -- of informing the graph Fourier transform about the communities without explicitly detecting them. Thereof, we show that the derived community-aware operators on signals, such as filtering or subsampling, provide a complementary view on the framework to the conventional one based on the Laplacian. Indeed, reduced signal variability within a community seems to be a valuable metric of important signal behavior, aside from its smoothness. Secondly, we explore the intricacies of a broader definition of a community -- a subgraph of any special interest, possibly identified through metadata on vertices instead of the underlying edge connectivity. Within this context, the goal is to understand the benefits of processing signals in a subgraph-restricted way. We design a new, more computationally stable type of Slepians -- bandlimited signals with energy concentrated on a subgraph. Consequently, we show that such bandlimited vectors can be successfully employed to identify a signal's oscillatory pattern localized in a subgraph of interest, by means of a modified filtering procedure. Findings from both lines of research confirm the need and benefits of a better understanding of the interaction between communities and graph signals.