Spikyball Sampling: Exploring Large Networks via an Inhomogeneous Filtered Diffusion
Studying real-world networks such as social networks or web networks is a challenge. These networks often combine a complex, highly connected structure together with a large size. We propose a new approach for large scale networks that is able to automatically sample user-defined relevant parts of a...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-10-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/13/11/275 |
| _version_ | 1797549319175274496 |
|---|---|
| author | Benjamin Ricaud Nicolas Aspert Volodymyr Miz |
| author_facet | Benjamin Ricaud Nicolas Aspert Volodymyr Miz |
| author_sort | Benjamin Ricaud |
| collection | DOAJ |
| description | Studying real-world networks such as social networks or web networks is a challenge. These networks often combine a complex, highly connected structure together with a large size. We propose a new approach for large scale networks that is able to automatically sample user-defined relevant parts of a network. Starting from a few selected places in the network and a reduced set of expansion rules, the method adopts a filtered breadth-first search approach, that expands through edges and nodes matching these properties. Moreover, the expansion is performed over a random subset of neighbors at each step to mitigate further the overwhelming number of connections that may exist in large graphs. This carries the image of a “spiky” expansion. We show that this approach generalize previous exploration sampling methods, such as Snowball or Forest Fire and extend them. We demonstrate its ability to capture groups of nodes with high interactions while discarding weakly connected nodes that are often numerous in social networks and may hide important structures. |
| first_indexed | 2024-03-10T15:13:00Z |
| format | Article |
| id | doaj.art-73f86f9fb53e4878a03afc679817849a |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-10T15:13:00Z |
| publishDate | 2020-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-73f86f9fb53e4878a03afc679817849a2023-11-20T19:12:50ZengMDPI AGAlgorithms1999-48932020-10-01131127510.3390/a13110275Spikyball Sampling: Exploring Large Networks via an Inhomogeneous Filtered DiffusionBenjamin Ricaud0Nicolas Aspert1Volodymyr Miz2LTS2, EPFL, Station 11, CH-1015 Lausanne, SwitzerlandLTS2, EPFL, Station 11, CH-1015 Lausanne, SwitzerlandLTS2, EPFL, Station 11, CH-1015 Lausanne, SwitzerlandStudying real-world networks such as social networks or web networks is a challenge. These networks often combine a complex, highly connected structure together with a large size. We propose a new approach for large scale networks that is able to automatically sample user-defined relevant parts of a network. Starting from a few selected places in the network and a reduced set of expansion rules, the method adopts a filtered breadth-first search approach, that expands through edges and nodes matching these properties. Moreover, the expansion is performed over a random subset of neighbors at each step to mitigate further the overwhelming number of connections that may exist in large graphs. This carries the image of a “spiky” expansion. We show that this approach generalize previous exploration sampling methods, such as Snowball or Forest Fire and extend them. We demonstrate its ability to capture groups of nodes with high interactions while discarding weakly connected nodes that are often numerous in social networks and may hide important structures.https://www.mdpi.com/1999-4893/13/11/275networksdata over networkssnowball samplinglarge scale |
| spellingShingle | Benjamin Ricaud Nicolas Aspert Volodymyr Miz Spikyball Sampling: Exploring Large Networks via an Inhomogeneous Filtered Diffusion Algorithms networks data over networks snowball sampling large scale |
| title | Spikyball Sampling: Exploring Large Networks via an Inhomogeneous Filtered Diffusion |
| title_full | Spikyball Sampling: Exploring Large Networks via an Inhomogeneous Filtered Diffusion |
| title_fullStr | Spikyball Sampling: Exploring Large Networks via an Inhomogeneous Filtered Diffusion |
| title_full_unstemmed | Spikyball Sampling: Exploring Large Networks via an Inhomogeneous Filtered Diffusion |
| title_short | Spikyball Sampling: Exploring Large Networks via an Inhomogeneous Filtered Diffusion |
| title_sort | spikyball sampling exploring large networks via an inhomogeneous filtered diffusion |
| topic | networks data over networks snowball sampling large scale |
| url | https://www.mdpi.com/1999-4893/13/11/275 |
| work_keys_str_mv | AT benjaminricaud spikyballsamplingexploringlargenetworksviaaninhomogeneousfiltereddiffusion AT nicolasaspert spikyballsamplingexploringlargenetworksviaaninhomogeneousfiltereddiffusion AT volodymyrmiz spikyballsamplingexploringlargenetworksviaaninhomogeneousfiltereddiffusion |