Comparison of large networks with sub-sampling strategies
Networks are routinely used to represent large data sets, making the comparison of networks a tantalizing research question in many areas. Techniques for such analysis vary from simply comparing network summary statistics to sophisticated but computationally expensive alignment-based approaches. Mos...
| Main Authors: | , , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Nature Publishing Group
2016
|
| _version_ | 1797060656652877824 |
|---|---|
| author | Ali, W Wegner, A Gaunt, R Deane, C Reinert, G |
| author_facet | Ali, W Wegner, A Gaunt, R Deane, C Reinert, G |
| author_sort | Ali, W |
| collection | OXFORD |
| description | Networks are routinely used to represent large data sets, making the comparison of networks a tantalizing research question in many areas. Techniques for such analysis vary from simply comparing network summary statistics to sophisticated but computationally expensive alignment-based approaches. Most existing methods either do not generalize well to different types of networks or do not provide a quantitative similarity score between networks. In contrast, alignment-free topology based network similarity scores empower us to analyse large sets of networks containing different types and sizes of data. Netdis is such a score that defines network similarity through the counts of small sub-graphs in the local neighbourhood of all nodes. Here, we introduce a sub-sampling procedure based on neighbourhoods which links naturally with the framework of network comparisons through local neighbourhood comparisons. Our theoretical arguments justify basing the Netdis statistic on a sample of similar-sized neighbourhoods. Our tests on empirical and synthetic datasets indicate that often only 10% of the neighbourhoods of a network suffice for optimal performance, leading to a drastic reduction in computational requirements. The sampling procedure is applicable even when only a small sample of the network is known, and thus provides a novel tool for network comparison of very large and potentially incomplete datasets. |
| first_indexed | 2024-03-06T20:20:11Z |
| format | Journal article |
| id | oxford-uuid:2d8992f0-165a-4237-9d5b-6b46bfa78d2e |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T20:20:11Z |
| publishDate | 2016 |
| publisher | Nature Publishing Group |
| record_format | dspace |
| spelling | oxford-uuid:2d8992f0-165a-4237-9d5b-6b46bfa78d2e2022-03-26T12:43:33ZComparison of large networks with sub-sampling strategiesJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:2d8992f0-165a-4237-9d5b-6b46bfa78d2eEnglishSymplectic Elements at OxfordNature Publishing Group2016Ali, WWegner, AGaunt, RDeane, CReinert, GNetworks are routinely used to represent large data sets, making the comparison of networks a tantalizing research question in many areas. Techniques for such analysis vary from simply comparing network summary statistics to sophisticated but computationally expensive alignment-based approaches. Most existing methods either do not generalize well to different types of networks or do not provide a quantitative similarity score between networks. In contrast, alignment-free topology based network similarity scores empower us to analyse large sets of networks containing different types and sizes of data. Netdis is such a score that defines network similarity through the counts of small sub-graphs in the local neighbourhood of all nodes. Here, we introduce a sub-sampling procedure based on neighbourhoods which links naturally with the framework of network comparisons through local neighbourhood comparisons. Our theoretical arguments justify basing the Netdis statistic on a sample of similar-sized neighbourhoods. Our tests on empirical and synthetic datasets indicate that often only 10% of the neighbourhoods of a network suffice for optimal performance, leading to a drastic reduction in computational requirements. The sampling procedure is applicable even when only a small sample of the network is known, and thus provides a novel tool for network comparison of very large and potentially incomplete datasets. |
| spellingShingle | Ali, W Wegner, A Gaunt, R Deane, C Reinert, G Comparison of large networks with sub-sampling strategies |
| title | Comparison of large networks with sub-sampling strategies |
| title_full | Comparison of large networks with sub-sampling strategies |
| title_fullStr | Comparison of large networks with sub-sampling strategies |
| title_full_unstemmed | Comparison of large networks with sub-sampling strategies |
| title_short | Comparison of large networks with sub-sampling strategies |
| title_sort | comparison of large networks with sub sampling strategies |
| work_keys_str_mv | AT aliw comparisonoflargenetworkswithsubsamplingstrategies AT wegnera comparisonoflargenetworkswithsubsamplingstrategies AT gauntr comparisonoflargenetworkswithsubsamplingstrategies AT deanec comparisonoflargenetworkswithsubsamplingstrategies AT reinertg comparisonoflargenetworkswithsubsamplingstrategies |