| 1. |
- Aslak, Ulf, et al.
(författare)
-
Constrained information flows in temporal networks reveal intermittent communities
- 2018
-
Ingår i: Physical review. E. - : American Physical Society. - 2470-0045 .- 2470-0053. ; 97:6
-
Tidskriftsartikel (refereegranskat)abstract
- Many real-world networks represent dynamic systems with interactions that change over time, often in uncoordinated ways and at irregular intervals. For example, university students connect in intermittent groups that repeatedly form and dissolve based on multiple factors, including their lectures, interests, and friends. Such dynamic systems can be represented as multilayer networkswhere each layer represents a snapshot of the temporal network. In this representation, it is crucial that the links between layers accurately capture real dependencies between those layers. Often, however, these dependencies are unknown. Therefore, current methods connect layers based on simplistic assumptions that do not capture node-level layer dependencies. For example, connecting every node to itself in other layers with the same weight can wipe out dependencies between intermittent groups, making it difficult or even impossible to identify them. In this paper, we present a principled approach to estimating node-level layer dependencies based on the network structure within each layer. We implement our node-level coupling method in the community detection framework Infomap and demonstrate its performance compared to current methods on synthetic and real temporal networks. We show that our approach more effectively constrains information inside multilayer communities so that Infomap can better recover planted groups in multilayer benchmark networks that represent multiple modeswith different groups and better identify intermittent communities in real temporal contact networks. These results suggest that node-level layer coupling can improve the modeling of information spreading in temporal networks and better capture intermittent community structure.
|
|
| 2. |
- Bae, Seung-Hee, et al.
(författare)
-
Scalable and Efficient Flow-Based Community Detection for Large-Scale Graph Analysis
- 2017
-
Ingår i: ACM Transactions on Knowledge Discovery from Data. - : Association for Computing Machinery (ACM). - 1556-4681 .- 1556-472X. ; 11:3
-
Tidskriftsartikel (refereegranskat)abstract
- Community detection is an increasingly popular approach to uncover important structures in large networks. Flow-based community detection methods rely on communication patterns of the network rather than structural properties to determine communities. The Infomap algorithm in particular optimizes a novel objective function called the map equation and has been shown to outperform other approaches in third-party benchmarks. However, Infomap and its variants are inherently sequential, limiting their use for large-scale graphs. In this article, we propose a novel algorithm to optimize the map equation called RelaxMap. RelaxMap provides two important improvements over Infomap: parallelization, so that the map equation can be optimized over much larger graphs, and prioritization, so that the most important work occurs first, iterations take less time, and the algorithm converges faster. We implement these techniques using OpenMP on shared-memory multicore systems, and evaluate our approach on a variety of graphs from standard graph clustering benchmarks as well as real graph datasets. Our evaluation shows that both techniques are effective: RelaxMap achieves 70% parallel efficiency on eight cores, and prioritization improves algorithm performance by an additional 20-50% on average, depending on the graph properties. Additionally, RelaxMap converges in the similar number of iterations and provides solutions of equivalent quality as the serial Infomap implementation.
|
|
| 3. |
- Bech, Morten L, et al.
(författare)
-
Mapping change in the overnight money market
- 2015
-
Ingår i: Physica A. - : Elsevier. - 0378-4371 .- 1873-2119. ; 424, s. 44-51
-
Tidskriftsartikel (refereegranskat)abstract
- We use an information-theoretic approach to describe changes in lending relationships between financial institutions around the time of the Lehman Brothers failure. Unlike previous work that conducts maximum likelihood estimation on undirected networks our analysis distinguishes between borrowers and lenders and looks for broader lending relationships (multi-bank lending cycles) that extend beyond the immediate counter-parties. We detect significant changes in lending patterns following implementation of the Interest on Required and Excess Reserves policy by the Federal Reserve in October 2008. Analysis of micro-scale rates of change in the data suggests these changes were triggered by the collapse of Lehman Brothers a few weeks before.
|
|
| 4. |
- Bernardo-Madrid, R., et al.
(författare)
-
Human activity is altering the world's zoogeographical regions
- 2019
-
Ingår i: Ecology Letters. - : Wiley. - 1461-023X .- 1461-0248. ; 22:8, s. 1297-1305
-
Tidskriftsartikel (refereegranskat)abstract
- Zoogeographical regions, or zooregions, are areas of the Earth defined by species pools that reflect ecological, historical and evolutionary processes acting over millions of years. Consequently, researchers have assumed that zooregions are robust and unlikely to change on a human timescale. However, the increasing number of human-mediated introductions and extinctions can challenge this assumption. By delineating zooregions with a network-based algorithm, here we show that introductions and extinctions are altering the zooregions we know today. Introductions are homogenising the Eurasian and African mammal zooregions and also triggering less intuitive effects in birds and amphibians, such as dividing and redefining zooregions representing the Old and New World. Furthermore, these Old and New World amphibian zooregions are no longer detected when considering introductions plus extinctions of the most threatened species. Our findings highlight the profound and far-reaching impact of human activity and call for identifying and protecting the uniqueness of biotic assemblages.
|
|
| 5. |
- Bohlin, Ludvig, et al.
(författare)
-
Robustness of journal rankings by network flows with different amounts of memory
- 2016
-
Ingår i: Journal of the Association for Information Science and Technology. - : Wiley. - 2330-1635 .- 2330-1643. ; 67:10, s. 2527-2535
-
Tidskriftsartikel (refereegranskat)abstract
- As the number of scientific journals has multiplied, journal rankings have become increasingly important for scientific decisions. From submissions and subscriptions to grants and hirings, researchers, policy makers, and funding agencies make important decisions influenced by journal rankings such as the ISI journal impact factor. Typically, the rankings are derived from the citation network between a selection of journals and unavoidably depend on this selection. However, little is known about how robust rankings are to the selection of included journals. We compare the robustness of three journal rankings based on network flows induced on citation networks. They model pathways of researchers navigating the scholarly literature, stepping between journals and remembering their previous steps to different degrees: zero-step memory as impact factor, one-step memory as Eigenfactor, and two-step memory, corresponding to zero-, first-, and second-order Markov models of citation flow between journals. We conclude that higher-order Markov models perform better and are more robust to the selection of journals. Whereas our analysis indicates that higher-order models perform better, the performance gain for higher-order Markov models comes at the cost of requiring more citation data over a longer time period.
|
|
| 6. |
- Bohlin, Ludvig, 1986-
(författare)
-
Toward higher-order network models
- 2018
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Complex systems play an essential role in our daily lives. These systems consist of many connected components that interact with each other. Consider, for example, society with billions of collaborating individuals, the stock market with numerous buyers and sellers that trade equities, or communication infrastructures with billions of phones, computers and satellites.The key to understanding complex systems is to understand the interaction patterns between their components - their networks. To create the network, we need data from the system and a model that organizes the given data in a network representation. Today's increasing availability of data and improved computational capacity for analyzing networks have created great opportunities for the network approach to further prosper. However, increasingly rich data also gives rise to new challenges that question the effectiveness of the conventional approach to modeling data as a network. In this thesis, we explore those challenges and provide methods for simplifying and highlighting important interaction patterns in network models that make use of richer data.Using data from real-world complex systems, we first show that conventional network modeling can provide valuable insights about the function of the underlying system. To explore the impact of using richer data in the network representation, we then expand the analysis for higher-order models of networks and show why we need to go beyond conventional models when there is data that allows us to do so. In addition, we also present a new framework for higher-order network modeling and analysis. We find that network models that capture richer data can provide more accurate representations of many real-world complex systems.
|
|
| 7. |
- Calatayud, Joaquín, et al.
(författare)
-
Exploring the solution landscape enables more reliable network community detection
- 2019
-
Ingår i: Physical review. E. - 2470-0045 .- 2470-0053. ; 100:5
-
Tidskriftsartikel (refereegranskat)abstract
- To understand how a complex system is organized and functions, researchers often identify communities in the system's network of interactions. Because it is practically impossible to explore all solutions to guarantee the best one, many community-detection algorithms rely on multiple stochastic searches. But for a given combination of network and stochastic algorithms, how many searches are sufficient to find a solution that is good enough? The standard approach is to pick a reasonably large number of searches and select the network partition with the highest quality or derive a consensus solution based on all network partitions. However, if different partitions have similar qualities such that the solution landscape is degenerate, the single best partition may miss relevant information, and a consensus solution may blur complementary communities. Here we address this degeneracy problem with coarse-grained descriptions of the solution landscape. We cluster network partitions based on their similarity and suggest an approach to determine the minimum number of searches required to describe the solution landscape adequately. To make good use of all partitions, we also propose different ways to explore the solution landscape, including a significance clustering procedure. We test these approaches on synthetic networks and a real-world network using two contrasting community-detection algorithms: The algorithm that can identify more general structures requires more searches, and networks with clearer community structures require fewer searches. We also find that exploring the coarse-grained solution landscape can reveal complementary solutions and enable more reliable community detection.
|
|
| 8. |
- De Domenico, Manlio, et al.
(författare)
-
Identifying Modular Flows on Multilayer Networks Reveals Highly Overlapping Organization in Interconnected Systems
- 2015
-
Ingår i: Physical Review X. - 2160-3308. ; 5:1
-
Tidskriftsartikel (refereegranskat)abstract
- To comprehend interconnected systems across the social and natural sciences, researchers have developed many powerful methods to identify functional modules. For example, with interaction data aggregated into a single network layer, flow-based methods have proven useful for identifying modular dynamics in weighted and directed networks that capture constraints on flow processes. However, many interconnected systems consist of agents or components that exhibit multiple layers of interactions, possibly from several different processes. Inevitably, representing this intricate network of networks as a single aggregated network leads to information loss and may obscure the actual organization. Here, we propose a method based on a compression of network flows that can identify modular flows both within and across layers in nonaggregated multilayer networks. Our numerical experiments on synthetic multilayer networks, with some layers originating from the same interaction process, show that the analysis fails in aggregated networks or when treating the layers separately, whereas the multilayer method can accurately identify modules across layers that originate from the same interaction process. We capitalize on our findings and reveal the community structure of two multilayer collaboration networks with topics as layers: scientists affiliated with the Pierre Auger Observatory and scientists publishing works on networks on the arXiv. Compared to conventional aggregated methods, the multilayer method uncovers connected topics and reveals smaller modules with more overlap that better capture the actual organization.
|
|
| 9. |
- Edler, Daniel, et al.
(författare)
-
Infomap Bioregions : Interactive Mapping of Biogeographical Regions from Species Distributions
- 2017
-
Ingår i: Systematic Biology. - : Oxford University Press (OUP). - 1063-5157 .- 1076-836X. ; 66:2, s. 197-204
-
Tidskriftsartikel (refereegranskat)abstract
- Biogeographical regions (bioregions) reveal how different sets of species are spatially grouped and therefore are important units for conservation, historical biogeography, ecology, and evolution. Several methods have been developed to identify bioregions based on species distribution data rather than expert opinion. One approach successfully applies network theory to simplify and highlight the underlying structure in species distributions. However, this method lacks tools for simple and efficient analysis. Here, we present Infomap Bioregions, an interactive web application that inputs species distribution data and generates bioregion maps. Species distributions may be provided as georeferenced point occurrences or range maps, and can be of local, regional, or global scale. The application uses a novel adaptive resolution method to make best use of often incomplete species distribution data. The results can be downloaded as vector graphics, shapefiles, or in table format. We validate the tool by processing large data sets of publicly available species distribution data of the world's amphibians using species ranges, and mammals using point occurrences. We then calculate the fit between the inferred bioregions and WWF ecoregions. As examples of applications, researchers can reconstruct ancestral ranges in historical biogeography or identify indicator species for targeted conservation.
|
|
| 10. |
- Edler, Daniel, et al.
(författare)
-
Mapping Higher-Order Network Flows in Memory and Multilayer Networks with Infomap
- 2017
-
Ingår i: Algorithms. - : MDPI AG. - 1999-4893. ; 10:4
-
Tidskriftsartikel (refereegranskat)abstract
- Comprehending complex systems by simplifying and highlighting important dynamical patterns requires modeling and mapping higher-order network flows. However, complex systems come in many forms and demand a range of representations, including memory and multilayer networks, which in turn call for versatile community-detection algorithms to reveal important modular regularities in the flows. Here we show that various forms of higher-order network flows can be represented in a unified way with networks that distinguish physical nodes for representing a complex system's objects from state nodes for describing flows between the objects. Moreover, these so-called sparse memory networks allow the information-theoretic community detection method known as the map equation to identify overlapping and nested flow modules in data from a range of different higher-order interactions such as multistep, multi-source, and temporal data. We derive the map equation applied to sparse memory networks and describe its search algorithm Infomap, which can exploit the flexibility of sparse memory networks. Together they provide a general solution to reveal overlapping modular patterns in higher-order flows through complex systems.
|
|
