umu.sePublications
Change search
Refine search result
12 1 - 50 of 51
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1. Aslak, Ulf
    et al.
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Lehmann, Sune
    Constrained information flows in temporal networks reveal intermittent communities2018In: Physical review. E, ISSN 2470-0045, E-ISSN 2470-0053, Vol. 97, no 6, article id 062312Article in journal (Refereed)
    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.

  • 2. Bae, Seung-Hee
    et al.
    Halperin, Daniel
    West, Jevin D.
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Howe, Bill
    Scalable and Efficient Flow-Based Community Detection for Large-Scale Graph Analysis2017In: ACM Transactions on Knowledge Discovery from Data, ISSN 1556-4681, E-ISSN 1556-472X, Vol. 11, no 3, article id 32Article in journal (Refereed)
    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.

  • 3. Bae, Seung-Hee
    et al.
    Halperin, Daniel
    West, Jevin
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Howe, Bill
    Scalable Flow-Based Community Detection for Large-Scale Network Analysis2013In: 2013 IEEE 13TH INTERNATIONAL CONFERENCE ON DATA MINING WORKSHOPS (ICDMW) / [ed] Ding, W Washio, T Xiong, H Karypis, G Thuraisingham, B Cook, D Wu, X, IEEE, 2013, p. 303-310Conference paper (Refereed)
    Abstract [en]

    Community-detection is a powerful approach to uncover important structures in large networks. Since networks often describe flow of some entity, flow-based community-detection methods are particularly interesting. One such algorithm is called Infomap, which optimizes the objective function known as the map equation. While Infomap is known to be an effective algorithm, its serial implementation cannot take advantage of multicore processing in modern computers. In this paper, we propose a novel parallel generalization of Infomap called RelaxMap. This algorithm relaxes concurrency assumptions to avoid lock overhead, achieving 70% parallel efficiency in shared-memory multicore experiments while exhibiting similar convergence properties and finding similar community structures as the serial algorithm. We evaluate our approach on a variety of real graph datasets as well as synthetic graphs produced by a popular graph generator used for benchmarking community detection algorithms. We describe the algorithm, the experiments, and some emerging research directions in high-performance community detection on massive graphs.

  • 4. Bech, Morten L
    et al.
    Bergstrom, Carl T
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Garratt, Rodney J
    Mapping change in the overnight money market2015In: Physica A: Statistical Mechanics and its Applications, ISSN 0378-4371, E-ISSN 1873-2119, Vol. 424, p. 44-51Article in journal (Refereed)
    Abstract [en]

    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.

  • 5.
    Bergstrom, Carl T
    et al.
    Department of Biology, University of Washington.
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Response to commentaries on “The transmission sense of information”: discussion note2011In: Biology & Philosophy, ISSN 0169-3867, Vol. 26, no 2, p. 195-200Article in journal (Refereed)
  • 6.
    Bergstrom, Carl T
    et al.
    Department of Biology, University of Washington.
    Rosvall, Martin
    Department of Biology, University of Washington.
    The transmission sense of information2011In: Biology & Philosophy, ISSN 0169-3867, E-ISSN 1572-8404, Vol. 26, no 2, p. 159-176Article in journal (Refereed)
    Abstract [en]

    Biologists rely heavily on the language of information, coding, and transmission that is commonplace in the field of information theory developed by Claude Shannon, but there is open debate about whether such language is anything more than facile metaphor. Philosophers of biology have argued that when biologists talk about information in genes and in evolution, they are not talking about the sort of information that Shannon’s theory addresses. First, philosophers have suggested that Shannon’s theory is only useful for developing a shallow notion of correlation, the so-called “causal sense” of information. Second, they typically argue that in genetics and evolutionary biology, information language is used in a “semantic sense,” whereas semantics are deliberately omitted from Shannon’s theory. Neither critique is well-founded. Here we propose an alternative to the causal and semantic senses of information: atransmission sense of information, in which an object X conveys information if the function of X is to reduce, by virtue of its sequence properties, uncertainty on the part of an agent who observes X. The transmission sense not only captures much of what biologists intend when they talk about information in genes, but also brings Shannon’s theory back to the fore. By taking the viewpoint of a communications engineer and focusing on the decision problem of how information is to be packaged for transport, this approach resolves several problems that have plagued the information concept in biology, and highlights a number of important features of the way that information is encoded, stored, and transmitted as genetic sequence.

  • 7.
    Bock Axelsen, Jacob
    et al.
    Niels Bohr Institute, Blegdansvej 17, DK 2100. Copenhagen, Denmark.
    Bernhardsson, Sebastian
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Sneppen, Kim
    Niels Bohr Institute, Blegdansvej 17, DK 2100. Copenhagen, Denmark.
    Trusina, Ala
    Niels Bohr Institute, Blegdansvej 17, DK 2100. Copenhagen, Denmark.
    Degree landscapes in scale-free networks2006In: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics: Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics, ISSN 1063-651X, E-ISSN 1095-3787, Vol. 74, p. 036119-Article in journal (Refereed)
    Abstract [en]

    We generalize the degree-organizational view of real-world networks with broad degree distributions in a landscape analog with mountains (high-degree nodes) and valleys (low-degree nodes). For example, correlated degrees between adjacent nodes correspond to smooth landscapes (social networks), hierarchical networks to one-mountain landscapes (the Internet), and degree-disassortative networks without hierarchical features to rough landscapes with several mountains. To quantify the topology, we here measure the widths of the mountains and the separation between different mountains. We also generate ridge landscapes to model networks organized under constraints imposed by the space the networks are embedded in, associated to spatial or in molecular networks to functional localization.

  • 8.
    Bohlin, Ludvig
    et al.
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Edler, Daniel
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Lancichinetti, Andrea
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Rosval, Martin
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Community Detection and Visualization of Networks with the Map Equation Framework2014In: Measuring Scholarly Impact: Methods and Practice / [ed] Ying Ding, Ronald Rousseau, Dietmar Wolfram, Springer, 2014, p. 3-34Chapter in book (Refereed)
    Abstract [en]

    Large networks contain plentiful information about the organization of a system. The challenge is to extract useful information buried in the structure of myriad nodes and links. Therefore, powerful tools for simplifying and highlighting important structures in networks are essential for comprehending their organization. Such tools are called community-detection methods and they are designed to identify strongly intraconnected modules that often correspond to important functional units. Here we describe one such method, known as the map equation, and its accompanying algorithms for finding, evaluating, and visualizing the modular organization of networks. The map equation framework is very flexible and can identify two-level, multi-level, and overlapping organization in weighted, directed, and multiplex networks with its search algorithm Infomap. Because the map equation framework operates on the flow induced by the links of a network, it naturally captures flow of ideas and citation flow, and is therefore well-suited for analysis of bibliometric networks.

  • 9.
    Bohlin, Ludvig
    et al.
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Stock Portfolio Structure of Individual Investors Infers Future Trading Behavior2014In: PLoS ONE, ISSN 1932-6203, E-ISSN 1932-6203, Vol. 9, no 7, p. e103006-Article in journal (Refereed)
    Abstract [en]

    Although the understanding of and motivation behind individual trading behavior is an important puzzle in finance, little is known about the connection between an investor's portfolio structure and her trading behavior in practice. In this paper, we investigate the relation between what stocks investors hold, and what stocks they buy, and show that investors with similar portfolio structures to a great extent trade in a similar way. With data from the central register of shareholdings in Sweden, we model the market in a similarity network, by considering investors as nodes, connected with links representing portfolio similarity. From the network, we find investor groups that not only identify different investment strategies, but also represent individual investors trading in a similar way. These findings suggest that the stock portfolios of investors hold meaningful information, which could be used to earn a better understanding of stock market dynamics.

  • 10.
    Bohlin, Ludvig
    et al.
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Viamontes Esquivel, Alcides
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Lancichinetti, Andrea
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Robustness of journal rankings by network flows with different amounts of memory2016In: 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)
    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.

  • 11. De Domenico, Manlio
    et al.
    Lancichinetti, Andrea
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Arenas, Alex
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Identifying Modular Flows on Multilayer Networks Reveals Highly Overlapping Organization in Interconnected Systems2015In: Physical Review X, ISSN 2160-3308, E-ISSN 2160-3308, Vol. 5, no 1, article id 011027Article in journal (Refereed)
    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.

  • 12.
    Derlén, Mattias
    et al.
    Umeå University, Faculty of Social Sciences, Department of Law.
    Lindholm, Johan
    Umeå University, Faculty of Social Sciences, Department of Law.
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Mirshahvalad, Atieh
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Coherence out of chaos: mapping European union law by running randomly through the maze of CJEU case law2013In: Europarättslig tidskrift, ISSN 1403-8722, no 3, p. 517-535Article in journal (Refereed)
    Abstract [no]

    Recent research has demonstrated the ability of network analysis to better understand law. In this study we apply network analysis to the case law of the European Court of Justice (CJEU) in order understand its role as a source of law. In doing so, we apply network analysis tools not previously used in legal scholarship, most significantly (i) a modified version of the PageRank algorithm, (ii) the Map Equation, and (iii) resampling to infer “missing” links. In the article we demonstrate that this method can help us to understand not only the CJEU’s case law but law generally.

  • 13.
    Edler, Daniel
    et al.
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Bohlin, Ludvig
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Mapping Higher-Order Network Flows in Memory and Multilayer Networks with Infomap2017In: Algorithms, ISSN 1999-4893, E-ISSN 1999-4893, Vol. 10, no 4, article id 112Article in journal (Refereed)
    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.

  • 14.
    Edler, Daniel
    et al.
    Umeå University, Faculty of Science and Technology, Department of Physics. Department of Biological and Environmental Sciences, University of Gothenburg, PO Box 461, SE-405 30 Gothenburg, Sweden.
    Guedes, Thais
    Zizka, Alexander
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Antonelli, Alexandre
    Infomap Bioregions: Interactive Mapping of Biogeographical Regions from Species Distributions2017In: Systematic Biology, ISSN 1063-5157, E-ISSN 1076-836X, Vol. 66, no 2, p. 197-204Article in journal (Refereed)
    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.

  • 15. Haring, Robin
    et al.
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Völker, Uwe
    Völzke, Henry
    Kroemer, Heyo
    Nauck, Matthias
    Wallaschofski, Henri
    A Network-Based Approach to Visualize Prevalence and Progression of Metabolic Syndrome Components2012In: PLoS ONE, ISSN 1932-6203, E-ISSN 1932-6203, Vol. 7, no 6, p. e39461-Article in journal (Refereed)
    Abstract [en]

    Background: The additional clinical value of clustering cardiovascular risk factors to define the metabolic syndrome (MetS) is still under debate. However, it is unclear which cardiovascular risk factors tend to cluster predominately and how individual risk factor states change over time. Methods & Results: We used data from 3,187 individuals aged 20-79 years from the population-based Study of Health in Pomerania for a network-based approach to visualize clustered MetS risk factor states and their change over a five-year follow-up period. MetS was defined by harmonized Adult Treatment Panel III criteria, and each individual's risk factor burden was classified according to the five MetS components at baseline and follow-up. We used the map generator to depict 32 (2(5)) different states and highlight the most important transitions between the 1,024 (32(2)) possible states in the weighted directed network. At baseline, we found the largest fraction (19.3%) of all individuals free of any MetS risk factors and identified hypertension (15.4%) and central obesity (6.3%), as well as their combination (19.0%), as the most common MetS risk factors. Analyzing risk factor flow over the five-year follow-up, we found that most individuals remained in their risk factor state and that low high-density lipoprotein cholesterol (HDL) (6.3%) was the most prominent additional risk factor beyond hypertension and central obesity. Also among individuals without any MetS risk factor at baseline, low HDL (3.5%), hypertension (2.1%), and central obesity (1.6%) were the first risk factors to manifest during follow-up. Conclusions: We identified hypertension and central obesity as the predominant MetS risk factor cluster and low HDL concentrations as the most prominent new onset risk factor.

  • 16.
    Holme, Petter
    et al.
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Komplexa system och nätverksfysik: Om hur saker hänger ihop ger andra saker deras egenskaper2009In: Kosmos, Fysikersamfundet , 2009Chapter in book (Other (popular science, discussion, etc.))
    Abstract [sv]

    Många system i samhället och naturen − från börskurser, ryktesspridning och etniska konflikter till snöflingor, epidemier och fågelflockar − får sina egenskaper av växelverkan mellan ett stort antal delar. Hur saker hänger ihop gör skillnad och forsk- ning om komplexa system handlar om att förstå hur makrosko- piska fenomen uppkommer från mikroskopiska interaktioner. Här gör vi några nedslag i detta tvärvetenskapliga område som har sin matematiska grund i statistisk fysik.

  • 17.
    Hotchkiss, E. R.
    et al.
    Umeå University, Faculty of Science and Technology, Department of Ecology and Environmental Sciences.
    Hall, R. O., Jr.
    Sponseller, R. A.
    Umeå University, Faculty of Science and Technology, Department of Ecology and Environmental Sciences.
    Butman, D.
    Klaminder, J.
    Umeå University, Faculty of Science and Technology, Department of Ecology and Environmental Sciences.
    Laudon, H.
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Karlsson, J.
    Umeå University, Faculty of Science and Technology, Department of Ecology and Environmental Sciences.
    Sources of and processes controlling CO2 emissions change with the size of streams and rivers2015In: Nature Geoscience, ISSN 1752-0894, E-ISSN 1752-0908, Vol. 8, no 9, p. 696-699Article in journal (Refereed)
    Abstract [en]

    Carbon dioxide (CO2) evasion from streams and rivers to the atmosphere represents a substantial flux in the global carbon cycle(1-3). The proportions of CO2 emitted from streams and rivers that come from terrestrially derived CO2 or from CO2 produced within freshwater ecosystems through aquatic metabolism are not well quantified. Here we estimated CO2 emissions from running waters in the contiguous United States, based on freshwater chemical and physical characteristics and modelled gas transfer velocities at 1463 United States Geological Survey monitoring sites. We then assessed CO2 production from aquatic metabolism, compiled from previously published measurements of net ecosystem production from 187 streams and rivers across the contiguous United States. We find that CO2 produced by aquatic metabolism contributes about 28% of CO2 evasion from streams and rivers with flows between 0.0001 and 19,000 m(3) s(-1). We mathematically modelled CO2 flux from groundwater into running waters along a stream-river continuum to evaluate the relationship between stream size and CO2 source. Terrestrially derived CO2 dominates emissions from small streams, and the percentage of CO2 emissions from aquatic metabolism increases with stream size. We suggest that the relative role of rivers as conduits for terrestrial CO2 efflux and as reactors mineralizing terrestrial organic carbon is a function of their size and connectivity with landscapes.

  • 18.
    Karimi, Fariba
    et al.
    Leibniz Institute for the Social Sciences, Cologne, Germany.
    Bohlin, Ludvig
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Samoilenko, Ann
    Leibniz-Institute for the Social Sciences, Cologne, Germany.
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Lancichinetti, Andrea
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Mapping bilateral information interests using the activity of Wikipedia editors2015In: Palgrave communications, ISSN 2055-1045, Vol. 1, p. 1-7, article id 15041Article in journal (Refereed)
    Abstract [en]

    We live in a global village where electronic communication has eliminated the geographical barriers of information exchange. The road is now open to worldwide convergence of information interests, shared values and understanding. Nevertheless, interests still vary between countries around the world. This raises important questions about what today’s world map of information interests actually looks like and what factors cause the barriers of information exchange between countries. To quantitatively construct a world map of information interests, we devise a scalable statistical model that identifies countries with similar information interests and measures the countries’ bilateral similarities. From the similarities we connect countries in a global network and find that countries can be mapped into 18 clusters with similar information interests. Through regression we find that language and religion best explain the strength of the bilateral ties and formation of clusters. Our findings provide a quantitative basis for further studies to better understand the complex interplay between shared interests and conflict on a global scale. The methodology can also be extended to track changes over time and capture important trends in global information exchange.

  • 19. Kawamoto, Tatsuro
    et al.
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Estimating the resolution limit of the map equation in community detection2015In: 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)
    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.

  • 20.
    Kheirkhahzadeh, Masoumeh
    et al.
    Umeå University, Faculty of Science and Technology, Department of Physics. Department of IT and Computer Engineering, Iran University of Science and Technology, Teheran, Iran.
    Lancichinetti, Andrea
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Efficient community detection of network flows for varying Markov times and bipartite networks2016In: Physical Review E, ISSN 2470-0045, Vol. 93, no 3, article id 032309Article in journal (Refereed)
    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.

  • 21.
    Lambiotte, R.
    et al.
    Univ Namur, Dept Math & Naxys, B-5000 Namur, Belgium .
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Ranking and clustering of nodes in networks with smart teleportation2012In: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics, ISSN 1539-3755, E-ISSN 1550-2376, Vol. 85, no 5, p. 056107-Article in journal (Refereed)
    Abstract [en]

    Random teleportation is a necessary evil for ranking and clustering directed networks based on random walks. Teleportation enables ergodic solutions, but the solutions must necessarily depend on the exact implementation and parametrization of the teleportation. For example, in the commonly used PageRank algorithm, the teleportation rate must trade off a heavily biased solution with a uniform solution. Here we show that teleportation to links rather than nodes enables a much smoother trade-off and effectively more robust results. We also show that, by not recording the teleportation steps of the random walker, we can further reduce the effect of teleportation with dramatic effects on clustering.

  • 22. Lambiotte, Renaud
    et al.
    Salnikov, Vsevolod
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Effect of memory on the dynamics of random walks on networks2015In: Journal of Complex Networks, ISSN 2051-1310, Vol. 3, no 2, p. 177-188Article in journal (Refereed)
    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.

  • 23.
    Lizana, Ludvig
    et al.
    Niels Bohr Institute.
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Sneppen, Kim
    Niels Bohr Institute.
    Time walkers and spatial dynamics of aging information2010In: Physical Review Letters, ISSN 0031-9007, E-ISSN 1079-7114, Vol. 104, p. 040603-Article in journal (Refereed)
    Abstract [en]

    The distribution of information is essential for a living system’s ability to coordinate and adapt. Random walkers are often used to model this distribution process and, in doing so, one effectively assumes that information maintains its relevance over time. But the value of information in social and biological systems often decays and must continuously be updated. To capture the spatial dynamics of aging information, we introduce time walkers. A time walker moves like a random walker, but interacts with traces left by other walkers, some representing older information, some newer. The traces form a navigable information landscape which we visualize as a river network. We quantify the dynamical properties of time walkers, and the quality of the information left behind, on a two-dimensional lattice. We show that searching in this landscape is superior to random searching.

  • 24.
    Minnhagen, Petter
    et al.
    Umeå University, Faculty of Science and Technology, Physics.
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Physics.
    Sneppen, Kim
    NORDITA, Blegdamsvej 17, DK 2100, Copenhagen, Denmark.
    Trusina, Ala
    Self-organization of structures and networks from merging and small-scale fluctuations2004In: Physica A: Statistical Mechanics and its Applications, ISSN 0378-4371, E-ISSN 1873-2119, Vol. 340, no 4, p. 725-732Article in journal (Refereed)
    Abstract [en]

    We discuss merging-and-creation as a self-organizing process for scale-free topologies in networks. Three power-law classes characterized by the power-law exponents 23 , 2 and 25 are identified and the process is generalized to networks. In the network context the merging can be viewed as a consequence of optimization related to more efficient signaling.

  • 25.
    Mirshahvalad, Atieh
    et al.
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Beauchesne, Olivier
    Science-Metrix.
    Archambault, Éric
    Science-Metrix.
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Resampling effects on significance analysis of network clustering and ranking2013In: PLoS ONE, ISSN 1932-6203, E-ISSN 1932-6203, Vol. 8, no 1, article id e53943Article in journal (Refereed)
    Abstract [en]

    Community detection helps us simplify the complex configuration of networks, but communities are reliable only if they are statistically significant. To detect statistically significant communities, a common approach is to resample the original network and analyze the communities. But resampling assumes independence between samples, while the components of a network are inherently dependent. Therefore, we must understand how breaking dependencies between resampled components affects the results of the significance analysis. Here we use scientific communication as a model system to analyze this effect. Our dataset includes citations among articles published in journals in the years 1984–2010. We compare parametric resampling of citations with non-parametric article resampling. While citation resampling breaks link dependencies, article resampling maintains such dependencies. We find that citation resampling underestimates the variance of link weights. Moreover, this underestimation explains most of the differences in the significance analysis of ranking and clustering. Therefore, when only link weights are available and article resampling is not an option, we suggest a simple parametric resampling scheme that generates link-weight variances close to the link-weight variances of article resampling. Nevertheless, when we highlight and summarize important structural changes in science, the more dependencies we can maintain in the resampling scheme, the earlier we can predict structural change. 

  • 26.
    Mirshahvalad, Atieh
    et al.
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Lindholm, Johan
    Umeå University, Faculty of Social Sciences, Department of Law.
    Derlén, Mattias
    Umeå University, Faculty of Social Sciences, Department of Law.
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Significant Communities in Large Sparse Networks2012In: PLoS ONE, ISSN 1932-6203, E-ISSN 1932-6203, Vol. 7, no 3, p. e33721-Article in journal (Refereed)
    Abstract [en]

    Researchers use community-detection algorithms to reveal large-scale organization in biological and social networks, but community detection is useful only if the communities are significant and not a result of noisy data. To assess the statistical significance of the network communities, or the robustness of the detected structure, one approach is to perturb the network structure by removing links and measure how much the communities change. However, perturbing sparse networks is challenging because they are inherently sensitive; they shatter easily if links are removed. Here we propose a simple method to perturb sparse networks and assess the significance of their communities. We generate resampled networks by adding extra links based on local information, then we aggregate the information from multiple resampled networks to find a coarse-grained description of significant clusters. In addition to testing our method on benchmark networks, we use our method on the sparse network of the European Court of Justice (ECJ) case law, to detect significant and insignificant areas of law. We use our significance analysis to draw a map of the ECJ case law network that reveals the relations between the areas of law.

  • 27.
    Mirshahvalad, Atieh
    et al.
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Reinforced communication and social navigation: Remember your friends and remember yourself2011In: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics, ISSN 1539-3755, E-ISSN 1550-2376, Vol. 84, no 3, p. 036102-Article in journal (Refereed)
    Abstract [en]

    In social systems, people communicate with each other and form groups based on their interests. The pattern of interactions, the network, and the ideas that flow on the network naturally evolve together. Researchers use simple models to capture the feedback between changing network patterns and ideas on the network, but little is understood about the role of past events in the feedback process. Here, we introduce a simple agent-based model to study the coupling between peoples' ideas and social networks, and better understand the role of history in dynamic social networks. We measure how information about ideas can be recovered from information about network structure and, the other way around, how information about network structure can be recovered from information about ideas. We find that it is, in general, easier to recover ideas from the network structure than vice versa.

  • 28.
    Mirshahvalad, Atieh
    et al.
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Viamontes Esquivel, Alcides
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Lizana, Ludvig
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Dynamics of interacting information waves in networks2014In: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics, ISSN 1539-3755, E-ISSN 1550-2376, Vol. 89, no 1, p. 012809-Article in journal (Refereed)
    Abstract [en]

    To better understand the inner workings of information spreading, network researchers often use simple models to capture the spreading dynamics. But most models only highlight the effect of local interactions on the global spreading of a single information wave, and ignore the effects of interactions between multiple waves. Here we take into account the effect of multiple interacting waves by using an agent-based model in which the interaction between information waves is based on their novelty. We analyzed the global effects of such interactions and found that information that actually reaches nodes reaches them faster. This effect is caused by selection between information waves: lagging waves die out and only leading waves survive. As a result, and in contrast to models with noninteracting information dynamics, the access to information decays with the distance from the source. Moreover, when we analyzed the model on various synthetic and real spatial road networks, we found that the decay rate also depends on the path redundancy and the effective dimension of the system. In general, the decay of the information wave frequency as a function of distance from the source follows a power-law distribution with an exponent between -0.2 for a two-dimensional system with high path redundancy and -0.5 for a tree-like system with no path redundancy. We found that the real spatial networks provide an infrastructure for information spreading that lies in between these two extremes. Finally, to better understand the mechanics behind the scaling results, we provide analytical calculations of the scaling for a one-dimensional system.

  • 29. Peixoto, Tiago P.
    et al.
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Modelling sequences and temporal networks with dynamic community structures2017In: Nature Communications, ISSN 2041-1723, E-ISSN 2041-1723, Vol. 8, article id 582Article in journal (Refereed)
    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.

  • 30.
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Physics.
    Information horizons in a complex world2006Doctoral thesis, comprehensive summary (Other academic)
    Abstract [en]

    The whole in a complex system is the sum of its parts, plus the interactions between the parts. Understanding social, biological, and economic systems therefore often depends on understanding their patterns of interactions---their networks. In this thesis, the approach is to understand complex systems by making simple network models with nodes and links. It is first of all an attempt to investigate how the communication over the network affects the network structure and, vice versa, how the network structure affects the conditions for communication.

    To explore the local mechanism behind network organization, we used simplified social systems and modeled the response to communication. Low communication levels resulted in random networks, whereas higher communication levels led to structured networks with most nodes having very few links and a few nodes having very many links. We also explored various models where nodes merge into bigger units, to reduce communication costs, and showed that these merging models give rise to the same kind of structured networks.

    In addition to this modeling of communication networks, we developed new ways to measure and characterize real-world networks. For example, we found that they in general favor communication on short distance, two-three steps away in the network, within what we call the information horizon.

  • 31.
    Rosvall, Martin
    et al.
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Axelsson, Daniel
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Bergstrom, Carl T
    Department of Biology, University of Washington.
    The map equation2009In: The European Physical Journal Special Topics, ISSN 1951-6355, E-ISSN 1951-6401, ISSN 1951-6401, Vol. 178, no 1, p. 13-23Article in journal (Refereed)
    Abstract [en]

    Many real-world networks are so large that we must simplify their structure before we can extract useful information about the systems they represent. As the tools for doing these simplifications proliferate within the network literature, researchers would benefit from some guidelines about which of the so-called community detection algorithms are most appropriate for the structures they are studying and the questions they are asking. Here we show that different methods highlight different aspects of a network's structure and that the the sort of information that we seek to extract about the system must guide us in our decision. For example, many community detection algorithms, including the popular modularity maximization approach, infer module assignments from an underlying model of the network formation process. However, we are not always as interested in how a system's network structure was formed, as we are in how a network's extant structure influences the system's behavior. To see how structure influences current behavior, we will recognize that links in a network induce movement across the network and result in system-wide interdependence. In doing so, we explicitly acknowledge that most networks carry flow. To highlight and simplify the network structure with respect to this flow, we use the map equation. We present an intuitive derivation of this flow-based and information-theoretic method and provide an interactive on-line application that anyone can use to explore the mechanics of the map equation. We also describe an algorithm and provide source code to efficiently decompose large weighted and directed networks based on the map equation.

  • 32.
    Rosvall, Martin
    et al.
    Department of Biology, University of Washington.
    Bergstrom, Carl
    Department of Biology, University of Washington.
    Mapping change in large networks2010In: PLoS ONE, ISSN 1932-6203, E-ISSN 1932-6203, Vol. 5, no 1Article in journal (Refereed)
    Abstract [en]

    Change is the very nature of interaction patterns in biology, technology, economy, and science itself: The interactions within and between organisms change; the air, ground, and sea traffic change; the global financial flow changes; and the scientific research front changes. With increasingly available data, networks and clustering tools have become important tools to comprehend instances of these large-scale structures. But blind to the difference between noise and trends in the data, these tools alone must fail when used to study change. Only if we can assign significance to the partition of single networks can we distinguish structural changes from fluctuations and assess how much confidence should we have in the changes. Here we show that bootstrap resampling accompanied by significance clustering provides a solution to this problem. We use the significance clustering to realize de Solla Price's vision of mapping the change in science.

  • 33.
    Rosvall, Martin
    et al.
    Department of Biology, University of Washington.
    Bergstrom, Carl T
    An information-theoretic framework for resolving community structure in complex networks2007In: Proceedings of the National Academy of Sciences of the United States of America, ISSN 0027-8424, E-ISSN 1091-6490, Vol. 104, no 18, p. 7327-7331Article in journal (Refereed)
    Abstract [en]

    To understand the structure of a large-scale biological, social, or technological network, it can be helpful to decompose the network into smaller subunits or modules. In this article, we develop an information-theoretic foundation for the concept of modularity in networks. We identify the modules of which the network is composed by finding an optimal compression of its topology, capitalizing on regularities in its structure. We explain the advantages of this approach and illustrate them by partitioning a number of real-world and model networks.

  • 34.
    Rosvall, Martin
    et al.
    Department of Biology, University of Washington.
    Bergstrom, Carl T
    Department of Biology, University of Washington.
    Maps of random walks on complex networks reveal community structure2008In: Proceedings of the National Academy of Sciences of the United States of America, ISSN 0027-8424, E-ISSN 1091-6490, Vol. 105, p. 1118-Article in journal (Refereed)
    Abstract [en]

    To comprehend the multipartite organization of large-scale biological and social systems, we introduce an information theoretic approach that reveals community structure in weighted and directed networks. We use the probability flow of random walks on a network as a proxy for information flows in the real system and decompose the network into modules by compressing a description of the probability flow. The result is a map that both simplifies and highlights the regularities in the structure and their relationships. We illustrate the method by making a map of scientific communication as captured in the citation patterns of >6,000 journals. We discover a multicentric organization with fields that vary dramatically in size and degree of integration into the network of science. Along the backbone of the network—including physics, chemistry, molecular biology, and medicine—information flows bidirectionally, but the map reveals a directional pattern of citation from the applied fields to the basic sciences.

  • 35.
    Rosvall, Martin
    et al.
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Bergstrom, Carl T
    Department of Biology, University of Washington.
    Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems2011In: PLoS ONE, ISSN 1932-6203, Vol. 6, no 4, p. e18209-Article in journal (Refereed)
    Abstract [en]

    To comprehend the hierarchical organization of large integrated systems, we introduce the hierarchical map equation, which reveals multilevel structures in networks. In this information-theoretic approach, we exploit the duality between compression and pattern detection; by compressing a description of a random walker as a proxy for real flow on a network, we find regularities in the network that induce this system-wide flow. Finding the shortest multilevel description of the random walker therefore gives us the best hierarchical clustering of the network — the optimal number of levels and modular partition at each level — with respect to the dynamics on the network. With a novel search algorithm, we extract and illustrate the rich multilevel organization of several large social and biological networks. For example, from the global air traffic network we uncover countries and continents, and from the pattern of scientific communication we reveal more than 100 scientific fields organized in four major disciplines: life sciences, physical sciences, ecology and earth sciences, and social sciences. In general, we find shallow hierarchical structures in globally interconnected systems, such as neural networks, and rich multilevel organizations in systems with highly separated regions, such as road networks.

  • 36.
    Rosvall, Martin
    et al.
    Niels Bohr Institute.
    Dodd, Ian
    Niels Bohr Institute.
    Krishna, Sandeep
    Niels Bohr Institute.
    Sneppen, Kim
    Niels Bohr Institute.
    Network models of phage-bacteria coevolution2006In: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics: Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics, ISSN 1063-651X, E-ISSN 1095-3787, Vol. 74, p. 066105-Article in journal (Refereed)
    Abstract [en]

    Bacteria and their bacteriophages are the most abundant, widespread, and diverse groups of biological entities on the planet. In an attempt to understand how the interactions between bacteria, virulent phages, and temperate phages might affect the diversity of these groups, we developed a stochastic network model for examining the coevolution of these ecologies. In our approach, nodes represent whole species or strains of bacteria or phages, rather than individuals, with “speciation” and extinction modeled by duplication and removal of nodes. Phage-bacteria links represent host-parasite relationships and temperate-virulent phage links denote prophage-encoded resistance. The effect of horizontal transfer of genetic information between strains was also included in the dynamical rules. The observed networks evolved in a highly dynamic fashion but the ecosystems were prone to collapse (one or more entire groups going extinct). Diversity could be stably maintained in the model only if the probability of speciation was independent of the diversity. Such an effect could be achieved in real ecosystems if the speciation rate is primarily set by the availability of ecological niches.

  • 37.
    Rosvall, Martin
    et al.
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Esquivel, Alcides V.
    Lancichinetti, Andrea
    Umeå University, Faculty of Science and Technology, Department of Physics.
    West, Jevin D.
    Lambiotte, Renaud
    Memory in network flows and its effects on spreading dynamics and community detection2014In: Nature Communications, ISSN 2041-1723, E-ISSN 2041-1723, Vol. 5, p. 4630-Article in journal (Refereed)
    Abstract [en]

    Random walks on networks is the standard tool for modelling spreading processes in social and biological systems. This first-order Markov approach is used in conventional community detection, ranking and spreading analysis, although it ignores a potentially important feature of the dynamics: where flow moves to may depend on where it comes from. Here we analyse pathways from different systems, and although we only observe marginal consequences for disease spreading, we show that ignoring the effects of second-order Markov dynamics has important consequences for community detection, ranking and information spreading. For example, capturing dynamics with a second-order Markov model allows us to reveal actual travel patterns in air traffic and to uncover multidisciplinary journals in scientific communication. These findings were achieved only by using more available data and making no additional assumptions, and therefore suggest that accounting for higher-order memory in network flows can help us better understand how real systems are organized and function.

  • 38.
    Rosvall, Martin
    et al.
    Umeå University, Faculty of Science and Technology, Physics.
    Grönlund, Andreas
    Umeå University, Faculty of Science and Technology, Physics.
    Minnhagen, Petter
    Umeå University, Faculty of Science and Technology, Physics.
    Sneppen, Kim
    NORDITA, Blegdamsvej 17, Dk 2100, Copenhagen, Denmark.
    Searchability of networks2005In: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics: Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics, ISSN 1063-651X, E-ISSN 1095-3787, Vol. 72, no 4, p. 046117-046125Article in journal (Refereed)
    Abstract [en]

    We investigate the searchability of complex systems in terms of their interconnectedness. Associating searchability with the number and size of branch points along the paths between the nodes, we find that scale-free networks are relatively difficult to search, and thus that the abundance of scale-free networks in nature and society may reflect an attempt to protect local areas in a highly interconnected network from nonrelated communication. In fact, starting from a random node, real-world networks with higher order organization like modular or hierarchical structure are even more difficult to navigate than random scale-free networks. The searchability at the node level opens the possibility for a generalized hierarchy measure that captures both the hierarchy in the usual terms of trees as in military structures, and the intrinsic hierarchical nature of topological hierarchies for scale-free networks as in the Internet.

  • 39.
    Rosvall, Martin
    et al.
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Minnhagen, Petter
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Sneppen, Kim
    Navigating networks with limited information2005In: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics: Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics, ISSN 1063-651X, E-ISSN 1095-3787, Vol. 71, no 6, p. 066111-Article in journal (Refereed)
    Abstract [en]

    We study navigation with limited information in networks and demonstrate that many real-world networks have a structure which can be described as favoring communication at short distance at the cost of constraining communication at long distance. This feature, which is robust and more evident with limited than with complete information, reflects both topological and possibly functional design characteristics. For example, the characteristics of the networks studied derived from a city and from the Internet are manifested through modular network designs. We also observe that directed navigation in typical networks requires remarkably little information on the level of individual nodes. By studying navigation or specific signaling, we take a complementary approach to the common studies of information transfer devoted to broadcasting of information in studies of virus spreading and the like.

  • 40.
    Rosvall, Martin
    et al.
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Sneppen, Kim
    Modeling self-organization of communication and topology in social networks2006In: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics: Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics, ISSN 1063-651X, E-ISSN 1095-3787, Vol. 74, no 1, p. 016108-Article in journal (Refereed)
    Abstract [en]

    This paper introduces a model of self-organization between communication and topology in social networks, with a feedback between different communication habits and the topology. To study this feedback, we let agents communicate to build a perception of a network and use this information to create strategic links. We observe a narrow distribution of links when the communication is low and a system with a broad distribution of links when the communication is high. We also analyze the outcome of chatting, cheating, and lying, as strategies to get better access to information in the network. Chatting, although only adopted by a few agents, gives a global gain in the system. Contrary, a global loss is inevitable in a system with too many liars.

  • 41.
    Rosvall, Martin
    et al.
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Sneppen, Kim
    The Niels Bohr Institute.
    Networks and our limited information horizon2007In: International Journal of Bifurcation and Chaos in Applied Sciences and Engineering, ISSN 0218-1274, Vol. 17, no 7, p. 2509-2515Article in journal (Refereed)
    Abstract [en]

    In this paper we quantify our limited information horizon, by measuring the information necessary to locate specific nodes in a network. To investigate different ways to overcome this horizon, and the interplay between communication and topology in social networks, we let agents communicate in a model society. Thereby they build a perception of the network that they can use to create strategic links to improve their standing in the network. We observe a narrow distribution of links when the communication is low and a network with a broad distribution of links when the communication is high.

  • 42.
    Rosvall, Martin
    et al.
    Department of Biology, University of Washington, Seattle, Washington 98195-1800, USA.
    Sneppen, Kim
    Niels Bohr Institute.
    Reinforced communication and social navigation generate groups in model networks2009In: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics: Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics, ISSN 1063-651X, E-ISSN 1095-3787, Vol. 79, no 2, p. 026111-026118Article in journal (Refereed)
    Abstract [en]

    To investigate the role of information flow in group formation, we introduce a model of communication and social navigation. We let agents gather information in an idealized network society and demonstrate that heterogeneous groups can evolve without presuming that individuals have different interests. In our scenario, individuals’ access to global information is constrained by local communication with the nearest neighbors on a dynamic network. The result is reinforced interests among like-minded agents in modular networks; the flow of information works as a glue that keeps individuals together. The model explains group formation in terms of limited information access and highlights global broadcasting of information as a way to counterbalance this fragmentation. To illustrate how the information constraints imposed by the communication structure affects future development of real-world systems, we extrapolate dynamics from the topology of four social networks.

  • 43.
    Rosvall, Martin
    et al.
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Sneppen, Kim
    Self-assembly of information in networks2006In: Europhysics letters, ISSN 0295-5075, E-ISSN 1286-4854, Vol. 74, no 6, p. 1109-1115Article in journal (Refereed)
    Abstract [en]

    We model self-assembly of information in networks to investigate necessary conditions for building a global perception of a system by local communication. Our approach is to let agents chat in a model system to self-organize distant communication pathways. We demonstrate that simple local rules allow agents to build a perception of the system, that is robust to dynamical changes and mistakes. We find that messages are most effectively forwarded in the presence of hubs, while transmission in hub-free networks is more robust against misinformation and failures.

  • 44.
    Rosvall, Martin
    et al.
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Viamontes Esquivel, Alcides
    Umeå University, Faculty of Science and Technology, Department of Physics.
    West, Jevin
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Lancichinetti, Andrea
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Lambiotte, Renaud
    University of Namur.
    Memory in network flows and its effects on community detection, ranking, and spreadingManuscript (preprint) (Other academic)
    Abstract [en]

    Random walks on networks is the standard tool for modelling spreading processes in social and biological systems. This first-order Markovapproach is used in conventional community detection, ranking, and spreading analysis although it ignores a potentially important feature ofthe dynamics: where flow moves to may depend on where it comes from. Here we analyse pathways from different systems, and while weonly observe marginal consequences for disease spreading, we show that ignoring the effects of second-order Markov dynamics has importantconsequences for community detection, ranking, and information spreading. For example, capturing dynamics with a second-order Markovmodel allows us to reveal actual travel patterns in air traffic and to uncover multidisciplinary journals in scientific communication. Thesefindings were achieved only by using more available data and making no additional assumptions, and therefore suggest that accounting forhigher-order memory in network flows can help us better understand how real systems are organized and function.

  • 45. Sneppen, Kim
    et al.
    Rosvall, Martin
    Niels Bohr Institute.
    A communication perspective on network topologies2006In: Progress of Theoretical Physics Supplement, ISSN 0375-9687, Vol. 165, p. 103-118Article in journal (Refereed)
    Abstract [en]

    We discuss topology of complex networks in the perspective of their ability to facilitate signaling.

  • 46.
    Sneppen, Kim
    et al.
    NORDITA, Blegdamsvej 17, 2100 Copenhagen Ø, Denmark.
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Physics.
    Trusina, Ala
    Umeå University, Faculty of Science and Technology, Physics.
    Minnhagen, Petter
    Umeå University, Faculty of Science and Technology, Physics.
    A simple model for self-organization of bipartite networks2004In: Europhysics Letters, ISSN 1286-4854, Vol. 67, no 3, p. 349-354Article in journal (Refereed)
    Abstract [en]

    We suggest a minimalistic model for directed networks and suggest an application to injection and merging of magnetic field lines. We obtain a network of connected donor and acceptor vertices with degree distribution 1/s2, and with dynamical reconnection events of size Δs occurring with frequency that scales as 1/Δs3. This suggests that the model is in the same universality class as the model with annihilation for self-organization in the solar atmosphere suggested by Hughes et al. (Phys. Rev. Lett. 90 (2003) 131101).

  • 47.
    Sneppen, Kim
    et al.
    NORDITA - Blegdamsvej 17, Dk 2100, Copenhagen, Denmark .
    Trusina, Ala
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Hide-and-seek on complex networks2005In: Europhys. Lett., ISSN 1286-4854, Vol. 69, no 5, p. 853-859Article in journal (Refereed)
    Abstract [en]

    Signaling pathways and networks determine the ability to communicate in systems ranging from living cells to human society. We investigate how the network structure constrains communication in social, man-made and biological networks. We find that human networks of governance and collaboration have predictable communication on tête-à-tête level, reflecting well-defined pathways. In contrast, communication pathways in the Internet are more distributed. For molecular networks, the communication ability in the single-celled yeast resembles the one of human networks, whereas the more complicated Drosophila is closer to the Internet. For all investigated networks, the global communication is worse than for their random counterparts, reflecting the fact that long-distance communication is disfavored.

  • 48.
    Sneppen, Kim
    et al.
    The Niels Bohr Institute.
    Trusina, Ala
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Measuring information networks2005In: Pramana (Bangalore), ISSN 0304-4289, E-ISSN 0973-7111, Vol. 64, no 6, p. 1121-1125Article in journal (Refereed)
    Abstract [en]

    Traffic and communication between different parts of a complex system are fundamental elements in maintaining its overall cooperativity. Because a complex system consists of many different parts, it matters where signals are transmitted. Thus signaling and traffic are in principle specific, with each message going from a unique sender to a specific recipient. In the current paper we review some measures of network topology that are related to its ability to direct specific communication.

  • 49. Trusina, Ala
    et al.
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Sneppen, Kim
    Communication boundaries in networks2005In: Physical Review Letters, ISSN 0031-9007, E-ISSN 1079-7114, Vol. 94, no 23, p. 238701-Article in journal (Refereed)
    Abstract [en]

    We investigate and quantify the interplay between topology and the ability to send specific signals in complex networks. We find that in a majority of investigated real-world networks the ability to communicate is favored by the network topology at small distances, but disfavored at larger distances. We further suggest how the ability to locate specific nodes can be improved if information associated with the overall traffic in the network is available.

     

  • 50.
    Viamontes Esquivel, Alcides
    et al.
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Bengtsson-Palme, Johan
    University of Gothenburg, Sahlgrenska Academy.
    Jonsson, Viktor
    Department of Mathematical Sciences, Chalmers University of Technology/University of Gothenburg.
    Boulund, Frederik
    Department of Mathematical Sciences, Chalmers University of Technology/University of Gothenburg, Göteborg.
    Rosvall, Martin
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Kristiansson, Erik
    Department of Mathematical Sciences, Chalmers University of Technology/University of Gothenburg, Göteborg.
    The genetic network of plasmid-mediated antibiotic multiresistanceManuscript (preprint) (Other academic)
12 1 - 50 of 51
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf