Efficient orbit-aware triad and quad census in directed and undirected graphs
Abstract The prevalence of select substructures is an indicator of network effects in applications such as social network analysis and systems biology. Moreover, subgraph statistics are pervasive in stochastic network models, and they need to be assessed repeatedly in MCMC sampling and estimation al...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
SpringerOpen
2017-06-01
|
| Series: | Applied Network Science |
| Subjects: | |
| Online Access: | http://link.springer.com/article/10.1007/s41109-017-0027-2 |
| _version_ | 1818677256257536000 |
|---|---|
| author | Mark Ortmann Ulrik Brandes |
| author_facet | Mark Ortmann Ulrik Brandes |
| author_sort | Mark Ortmann |
| collection | DOAJ |
| description | Abstract The prevalence of select substructures is an indicator of network effects in applications such as social network analysis and systems biology. Moreover, subgraph statistics are pervasive in stochastic network models, and they need to be assessed repeatedly in MCMC sampling and estimation algorithms. We present a new approach to count all induced and non-induced four-node subgraphs (the quad census) on a per-node and per-edge basis, complete with a separation into their non-automorphic roles in these subgraphs. It is the first approach to do so in a unified manner, and is based on only a clique-listing subroutine. Computational experiments indicate that, despite its simplicity, the approach outperforms previous, less general approaches. By way of the more presentable triad census, we additionally show how to extend the quad census to directed graphs. As a byproduct we obtain the asymptotically fastest triad census algorithm to date. |
| first_indexed | 2024-12-17T08:56:29Z |
| format | Article |
| id | doaj.art-f739d94bce1c419cadb527d82b269c17 |
| institution | Directory Open Access Journal |
| issn | 2364-8228 |
| language | English |
| last_indexed | 2024-12-17T08:56:29Z |
| publishDate | 2017-06-01 |
| publisher | SpringerOpen |
| record_format | Article |
| series | Applied Network Science |
| spelling | doaj.art-f739d94bce1c419cadb527d82b269c172022-12-21T21:55:56ZengSpringerOpenApplied Network Science2364-82282017-06-012111710.1007/s41109-017-0027-2Efficient orbit-aware triad and quad census in directed and undirected graphsMark Ortmann0Ulrik Brandes1Department of Computer & Information Science, University of KonstanzDepartment of Computer & Information Science, University of KonstanzAbstract The prevalence of select substructures is an indicator of network effects in applications such as social network analysis and systems biology. Moreover, subgraph statistics are pervasive in stochastic network models, and they need to be assessed repeatedly in MCMC sampling and estimation algorithms. We present a new approach to count all induced and non-induced four-node subgraphs (the quad census) on a per-node and per-edge basis, complete with a separation into their non-automorphic roles in these subgraphs. It is the first approach to do so in a unified manner, and is based on only a clique-listing subroutine. Computational experiments indicate that, despite its simplicity, the approach outperforms previous, less general approaches. By way of the more presentable triad census, we additionally show how to extend the quad census to directed graphs. As a byproduct we obtain the asymptotically fastest triad census algorithm to date.http://link.springer.com/article/10.1007/s41109-017-0027-2GraphletsMotifsSubgraph censusGraph statistics |
| spellingShingle | Mark Ortmann Ulrik Brandes Efficient orbit-aware triad and quad census in directed and undirected graphs Applied Network Science Graphlets Motifs Subgraph census Graph statistics |
| title | Efficient orbit-aware triad and quad census in directed and undirected graphs |
| title_full | Efficient orbit-aware triad and quad census in directed and undirected graphs |
| title_fullStr | Efficient orbit-aware triad and quad census in directed and undirected graphs |
| title_full_unstemmed | Efficient orbit-aware triad and quad census in directed and undirected graphs |
| title_short | Efficient orbit-aware triad and quad census in directed and undirected graphs |
| title_sort | efficient orbit aware triad and quad census in directed and undirected graphs |
| topic | Graphlets Motifs Subgraph census Graph statistics |
| url | http://link.springer.com/article/10.1007/s41109-017-0027-2 |
| work_keys_str_mv | AT markortmann efficientorbitawaretriadandquadcensusindirectedandundirectedgraphs AT ulrikbrandes efficientorbitawaretriadandquadcensusindirectedandundirectedgraphs |