Unwinding the hairball graph: pruning algorithms for weighted complex networks
| Autor: | Navid Dianati |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2015 |
| Předmět: |
0301 basic medicine
Social and Information Networks (cs.SI) FOS: Computer and information sciences Physics - Physics and Society Null model FOS: Physical sciences Computer Science - Social and Information Networks Physics and Society (physics.soc-ph) Complex network 01 natural sciences Thresholding Marginal likelihood Giant component 03 medical and health sciences 030104 developmental biology Filter (video) 0103 physical sciences Multiple edges 010306 general physics Algorithm Pruning (morphology) Mathematics |
| Popis: | Empirical networks of weighted dyadic relations often contain "noisy" edges that alter the global characteristics of the network and obfuscate the most important structures therein. Graph pruning is the process of identifying the most significant edges according to a generative null model and extracting the subgraph consisting of those edges. Here, we focus on integer-weighted graphs commonly arising when weights count the occurrences of an "event" relating the nodes. We introduce a simple and intuitive null model related to the configuration model of network generation and derive two significance filters from it: the marginal likelihood filter (MLF) and the global likelihood filter (GLF). The former is a fast algorithm assigning a significance score to each edge based on the marginal distribution of edge weights, whereas the latter is an ensemble approach which takes into account the correlations among edges. We apply these filters to the network of air traffic volume between US airports and recover a geographically faithful representation of the graph. Furthermore, compared with thresholding based on edge weight, we show that our filters extract a larger and significantly sparser giant component. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|