Multivariate algorithmics for finding cohesive subnetworks (Q1736776)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Multivariate algorithmics for finding cohesive subnetworks |
scientific article; zbMATH DE number 7042330
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Multivariate algorithmics for finding cohesive subnetworks |
scientific article; zbMATH DE number 7042330 |
Statements
Multivariate algorithmics for finding cohesive subnetworks (English)
0 references
26 March 2019
0 references
Summary: Community detection is an important task in the analysis of biological, social or technical networks. We survey different models of cohesive graphs, commonly referred to as \textit{clique relaxations}, that are used in the detection of network communities. For each clique relaxation, we give an overview of basic model properties and of the complexity of the problem of finding large cohesive subgraphs under this model. Since this problem is usually NP-hard, we focus on combinatorial fixed-parameter algorithms exploiting typical structural properties of input networks.
0 references
clique relaxations
0 references
dense subgraphs
0 references
NP-hard problem
0 references
network communities
0 references
fixed-parameter algorithms
0 references
0 references
0 references
0 references
0.7817809581756592
0 references
0.7662800550460815
0 references
0.7618306875228882
0 references
0.7443621158599854
0 references
0.7410387396812439
0 references
