umu.sePublications
Change search
Link to record
Permanent link

Direct link
BETA
Alternative names
Publications (10 of 51) Show all publications
Aslak, U., Rosvall, M. & Lehmann, S. (2018). Constrained information flows in temporal networks reveal intermittent communities. Physical review. E, 97(6), Article ID 062312.
Open this publication in new window or tab >>Constrained information flows in temporal networks reveal intermittent communities
2018 (English)In: Physical review. E, ISSN 2470-0045, E-ISSN 2470-0053, Vol. 97, no 6, article id 062312Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
American Physical Society, 2018
National Category
Other Physics Topics
Identifiers
urn:nbn:se:umu:diva-150774 (URN)10.1103/PhysRevE.97.062312 (DOI)000436041200005 ()30011557 (PubMedID)
Available from: 2018-08-31 Created: 2018-08-31 Last updated: 2018-08-31Bibliographically approved
Edler, D., Guedes, T., Zizka, A., Rosvall, M. & Antonelli, A. (2017). Infomap Bioregions: Interactive Mapping of Biogeographical Regions from Species Distributions. Systematic Biology, 66(2), 197-204
Open this publication in new window or tab >>Infomap Bioregions: Interactive Mapping of Biogeographical Regions from Species Distributions
Show others...
2017 (English)In: Systematic Biology, ISSN 1063-5157, E-ISSN 1076-836X, Vol. 66, no 2, p. 197-204Article in journal (Refereed) Published
Abstract [en]

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.

Keywords
Biogeography, bioregionalization, conservation, mapping
National Category
Biological Systematics
Identifiers
urn:nbn:se:umu:diva-133791 (URN)10.1093/sysbio/syw087 (DOI)000397703800007 ()27694311 (PubMedID)
Available from: 2017-04-24 Created: 2017-04-24 Last updated: 2018-06-09Bibliographically approved
Edler, D., Bohlin, L. & Rosvall, M. (2017). Mapping Higher-Order Network Flows in Memory and Multilayer Networks with Infomap. Algorithms, 10(4), Article ID 112.
Open this publication in new window or tab >>Mapping Higher-Order Network Flows in Memory and Multilayer Networks with Infomap
2017 (English)In: Algorithms, ISSN 1999-4893, E-ISSN 1999-4893, Vol. 10, no 4, article id 112Article in journal (Refereed) Published
Abstract [en]

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.

Keywords
community detection, Infomap, higher-order network flows, overlapping communities, multilayer tworks, memory networks
National Category
Computer Sciences
Identifiers
urn:nbn:se:umu:diva-144114 (URN)10.3390/a10040112 (DOI)000419169400004 ()
Available from: 2018-01-26 Created: 2018-01-26 Last updated: 2018-06-09Bibliographically approved
Peixoto, T. P. & Rosvall, M. (2017). Modelling sequences and temporal networks with dynamic community structures. Nature Communications, 8, Article ID 582.
Open this publication in new window or tab >>Modelling sequences and temporal networks with dynamic community structures
2017 (English)In: Nature Communications, ISSN 2041-1723, E-ISSN 2041-1723, Vol. 8, article id 582Article in journal (Refereed) Published
Abstract [en]

In evolving complex systems such as air traffic and social organisations, collective effects emerge from their many components' dynamic interactions. While the dynamic interactions can be represented by temporal networks with nodes and links that change over time, they remain highly complex. It is therefore often necessary to use methods that extract the temporal networks' large-scale dynamic community structure. However, such methods are subject to overfitting or suffer from effects of arbitrary, a priori-imposed timescales, which should instead be extracted from data. Here we simultaneously address both problems and develop a principled data-driven method that determines relevant timescales and identifies patterns of dynamics that take place on networks, as well as shape the networks themselves. We base our method on an arbitrary-order Markov chain model with community structure, and develop a nonparametric Bayesian inference framework that identifies the simplest such model that can explain temporal interaction data.

Place, publisher, year, edition, pages
NATURE PUBLISHING GROUP, 2017
National Category
Computer Sciences
Identifiers
urn:nbn:se:umu:diva-140461 (URN)10.1038/s41467-017-00148-9 (DOI)000411166800001 ()28928409 (PubMedID)
Available from: 2017-10-25 Created: 2017-10-25 Last updated: 2018-06-09Bibliographically approved
Bae, S.-H., Halperin, D., West, J. D., Rosvall, M. & Howe, B. (2017). Scalable and Efficient Flow-Based Community Detection for Large-Scale Graph Analysis. ACM Transactions on Knowledge Discovery from Data, 11(3), Article ID 32.
Open this publication in new window or tab >>Scalable and Efficient Flow-Based Community Detection for Large-Scale Graph Analysis
Show others...
2017 (English)In: ACM Transactions on Knowledge Discovery from Data, ISSN 1556-4681, E-ISSN 1556-472X, Vol. 11, no 3, article id 32Article in journal (Refereed) Published
Abstract [en]

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.

National Category
Other Physics Topics
Identifiers
urn:nbn:se:umu:diva-134746 (URN)10.1145/2992785 (DOI)000399725200007 ()
Available from: 2017-05-11 Created: 2017-05-11 Last updated: 2018-06-09Bibliographically approved
Kheirkhahzadeh, M., Lancichinetti, A. & Rosvall, M. (2016). Efficient community detection of network flows for varying Markov times and bipartite networks. Physical Review E, 93(3), Article ID 032309.
Open this publication in new window or tab >>Efficient community detection of network flows for varying Markov times and bipartite networks
2016 (English)In: Physical Review E, ISSN 2470-0045, Vol. 93, no 3, article id 032309Article in journal (Refereed) Published
Abstract [en]

Community detection of network flows conventionally assumes one-step dynamics on the links. For sparse networks and interest in large-scale structures, longer timescales may be more appropriate. Oppositely, for large networks and interest in small-scale structures, shorter timescales may be better. However, current methods for analyzing networks at different timescales require expensive and often infeasible network reconstructions. To overcome this problem, we introduce a method that takes advantage of the inner workings of the map equation and evades the reconstruction step. This makes it possible to efficiently analyze large networks at different Markov times with no extra overhead cost. The method also evades the costly unipartite projection for identifying flow modules in bipartite networks.

National Category
Other Physics Topics
Identifiers
urn:nbn:se:umu:diva-120647 (URN)10.1103/PhysRevE.93.032309 (DOI)000371745800002 ()
Available from: 2016-08-02 Created: 2016-05-18 Last updated: 2018-06-07Bibliographically approved
Bohlin, L., Viamontes Esquivel, A., Lancichinetti, A. & Rosvall, M. (2016). Robustness of journal rankings by network flows with different amounts of memory. Journal of the Association for Information Science and Technology, 67(10), 2527-2535
Open this publication in new window or tab >>Robustness of journal rankings by network flows with different amounts of memory
2016 (English)In: Journal of the Association for Information Science and Technology, ISSN 2330-1635, E-ISSN 2330-1643, Vol. 67, no 10, p. 2527-2535Article in journal (Refereed) Published
Abstract [en]

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.

National Category
Other Physics Topics Information Studies
Research subject
Physics
Identifiers
urn:nbn:se:umu:diva-89147 (URN)10.1002/asi.23582 (DOI)000384509100016 ()
Note

Originally published in thesis in manuscript form.

Available from: 2014-05-22 Created: 2014-05-22 Last updated: 2018-06-07Bibliographically approved
Lambiotte, R., Salnikov, V. & Rosvall, M. (2015). Effect of memory on the dynamics of random walks on networks. Journal of Complex Networks, 3(2), 177-188
Open this publication in new window or tab >>Effect of memory on the dynamics of random walks on networks
2015 (English)In: Journal of Complex Networks, ISSN 2051-1310, Vol. 3, no 2, p. 177-188Article in journal (Refereed) Published
Abstract [en]

Pathways of diffusion observed in real-world systems often require stochastic processes going beyond first-order Markov models, as implicitly assumed in network theory. In this work, we focus on second-order Markov models, and derive an analytical expression for the effect of memory on the spectral gap and thus, equivalently, on the characteristic time needed for the stochastic process to asymptotically reach equilibrium. Perturbation analysis shows that standard first-order Markov models can either overestimate or underestimate the diffusion rate of flows across the modular structure of a system captured by a second-order Markov network. We test the theoretical predictions on a toy example and on numerical data, and discuss their implications for network theory, in particular in the case of temporal or multiplex networks.

Place, publisher, year, edition, pages
Oxford University Press, 2015
Keywords
random walks, spectral gap, non-Markovian process, temporal networks
National Category
Other Physics Topics
Identifiers
urn:nbn:se:umu:diva-151314 (URN)10.1093/comnet/cnu017 (DOI)000434604700002 ()
Available from: 2018-08-31 Created: 2018-08-31 Last updated: 2018-08-31Bibliographically approved
Kawamoto, T. & Rosvall, M. (2015). Estimating the resolution limit of the map equation in community detection. Physical Review E. Statistical, Nonlinear, and Soft Matter Physics, 91(1), 012809
Open this publication in new window or tab >>Estimating the resolution limit of the map equation in community detection
2015 (English)In: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics, ISSN 1539-3755, E-ISSN 1550-2376, Vol. 91, no 1, p. 012809-Article in journal (Refereed) Published
Abstract [en]

A community detection algorithm is considered to have a resolution limit if the scale of the smallest modules that can be resolved depends on the size of the analyzed subnetwork. The resolution limit is known to prevent some community detection algorithms from accurately identifying the modular structure of a network. In fact, any global objective function for measuring the quality of a two-level assignment of nodes into modules must have some sort of resolution limit or an external resolution parameter. However, it is yet unknown how the resolution limit affects the so-called map equation, which is known to be an efficient objective function for community detection. We derive an analytical estimate and conclude that the resolution limit of the map equation is set by the total number of links between modules instead of the total number of links in the full network as for modularity. This mechanism makes the resolution limit much less restrictive for the map equation than for modularity; in practice, it is orders of magnitudes smaller. Furthermore, we argue that the effect of the resolution limit often results from shoehorning multilevel modular structures into two-level descriptions. As we show, the hierarchical map equation effectively eliminates the resolution limit for networks with nested multilevel modular structures.

National Category
Fusion, Plasma and Space Physics
Identifiers
urn:nbn:se:umu:diva-100132 (URN)10.1103/PhysRevE.91.012809 (DOI)000348764300008 ()
Available from: 2015-03-03 Created: 2015-02-24 Last updated: 2018-06-07Bibliographically approved
De Domenico, M., Lancichinetti, A., Arenas, A. & Rosvall, M. (2015). Identifying Modular Flows on Multilayer Networks Reveals Highly Overlapping Organization in Interconnected Systems. Physical Review X, 5(1), Article ID 011027.
Open this publication in new window or tab >>Identifying Modular Flows on Multilayer Networks Reveals Highly Overlapping Organization in Interconnected Systems
2015 (English)In: Physical Review X, ISSN 2160-3308, E-ISSN 2160-3308, Vol. 5, no 1, article id 011027Article in journal (Refereed) Published
Abstract [en]

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.

National Category
Other Physics Topics
Identifiers
urn:nbn:se:umu:diva-102454 (URN)10.1103/PhysRevX.5.011027 (DOI)000351284800001 ()
Available from: 2015-05-20 Created: 2015-04-26 Last updated: 2018-06-07Bibliographically approved
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0002-7181-9940

Search in DiVA

Show all publications