Isolation concepts applied to temporal clique enumeration
| Autor: | Rolf Niedermeier, Hendrik Molter, Malte Renken |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Clique
Theoretical computer science Sociology and Political Science Social Psychology Degree (graph theory) Computer science Communication Parameterized complexity Context (language use) 0102 computer and information sciences 02 engineering and technology 01 natural sciences 010201 computation theory & mathematics 020204 information systems 0202 electrical engineering electronic engineering information engineering Enumeration Graph (abstract data type) Isolation (database systems) Social network analysis |
| Zdroj: | Network Science. 9:S83-S105 |
| ISSN: | 2050-1250 2050-1242 |
| DOI: | 10.1017/nws.2020.38 |
| Popis: | Isolation is a concept originally conceived in the context of clique enumeration in static networks, mostly used to model communities that do not have much contact to the outside world. Herein, a clique is considered isolated if it has few edges connecting it to the rest of the graph. Motivated by recent work on enumerating cliques in temporal networks, we transform the isolation concept to the temporal setting. We discover that the addition of the time dimension leads to six distinct natural isolation concepts. Our main contribution is the development of parameterized enumeration algorithms for five of these six isolation types for clique enumeration, employing the parameter “degree of isolation.” In a nutshell, this means that the more isolated these cliques are, the faster we can find them. On the empirical side, we implemented and tested these algorithms on (temporal) social network data, obtaining encouraging results. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|