**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Community structure

Summary

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

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related units

Related people

No results

No results

Related publications (12)

Loading

Loading

Loading

Related courses (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.

Related lectures (17)

Related concepts (6)

In mathematics, computer science and network science, network theory is a part of graph theory. It defines networks as graphs where the nodes or edges possess attributes. Network theory analyses th

Network science is an academic field which studies complex networks such as telecommunication networks, computer networks, biological networks, cognitive and semantic networks, and social networks, co

In the context of network theory, a complex network is a graph (network) with non-trivial topological features—features that do not occur in simple networks such as lattices or random graphs bu

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.