Ê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 Graph Search.
Concept
Stochastic block model
Résumé
The stochastic block model is a generative model for random graphs. This model tends to produce graphs containing communities, subsets of nodes characterized by being connected with one another with particular edge densities. For example, edges may be more common within communities than between communities. Its mathematical formulation has been firstly introduced in 1983 in the field of social network by Paul W. Holland et al. The stochastic block model is important in statistics, machine learning, and network science, where it serves as a useful benchmark for the task of recovering community structure in graph data.
The stochastic block model takes the following parameters:
The number of vertices;
a partition of the vertex set into disjoint subsets , called communities;
a symmetric matrix of edge probabilities.
The edge set is then sampled at random as follows: any two vertices and are connected by an edge with probability . An example problem is: given a graph with vertices, where the edges are sampled as described, recover the groups .
If the probability matrix is a constant, in the sense that for all , then the result is the Erdős–Rényi model . This case is degenerate—the partition into communities becomes irrelevant—but it illustrates a close relationship to the Erdős–Rényi model.
The planted partition model is the special case that the values of the probability matrix are a constant on the diagonal and another constant off the diagonal. Thus two vertices within the same community share an edge with probability , while two vertices in different communities share an edge with probability . Sometimes it is this restricted model that is called the stochastic block model. The case where is called an assortative model, while the case is called disassortative.
Returning to the general stochastic block model, a model is called strongly assortative if whenever : all diagonal entries dominate all off-diagonal entries. A model is called weakly assortative if whenever : each diagonal entry is only required to dominate the rest of its own row and column.
Source officielle
À propos de ce résultat
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.