Random intersection graphs with communities
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2018
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918286301593600 |
|---|---|
| author | van der Hofstad, Remco Komjathy, Julia Vadon, Viktoria |
| author_facet | van der Hofstad, Remco Komjathy, Julia Vadon, Viktoria |
| contents | Random intersection graphs model networks with communities, assuming an underlying bipartite structure of groups and individuals, where these groups may overlap. Group memberships are generated through the bipartite configuration model. Conditionally on the group memberships, the classical random intersection graph is obtained by connecting individuals when they are together in at least one group. We generalize this definition, allowing for arbitrary community structures within the groups.
In our new model, groups might overlap and they have their own internal structure described by a graph, the classical setting corresponding to groups being complete graphs. Our model turns out to be tractable. We analyze the overlapping structure of the communities, derive the asymptotic degree distribution and the local clustering coefficient. These proofs rely on local weak convergence, which also implies that subgraph counts converge. We further exploit the connection to the bipartite configuration model, for which we also prove local weak convergence, and which is interesting in its own right. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1809_02514 |
| institution | arXiv |
| publishDate | 2018 |
| record_format | arxiv |
| spellingShingle | Random intersection graphs with communities van der Hofstad, Remco Komjathy, Julia Vadon, Viktoria Probability Combinatorics 60C05, 05C80, 90B15 Random intersection graphs model networks with communities, assuming an underlying bipartite structure of groups and individuals, where these groups may overlap. Group memberships are generated through the bipartite configuration model. Conditionally on the group memberships, the classical random intersection graph is obtained by connecting individuals when they are together in at least one group. We generalize this definition, allowing for arbitrary community structures within the groups. In our new model, groups might overlap and they have their own internal structure described by a graph, the classical setting corresponding to groups being complete graphs. Our model turns out to be tractable. We analyze the overlapping structure of the communities, derive the asymptotic degree distribution and the local clustering coefficient. These proofs rely on local weak convergence, which also implies that subgraph counts converge. We further exploit the connection to the bipartite configuration model, for which we also prove local weak convergence, and which is interesting in its own right. |
| title | Random intersection graphs with communities |
| topic | Probability Combinatorics 60C05, 05C80, 90B15 |
| url | https://arxiv.org/abs/1809.02514 |