Search

This work extends the randomized shortest paths (RSP) model by investigating the net flow RSP and adding capacity constraints on edge flows. The standard RSP is a model of movement, or spread, through a network interpolating between a random-walk and a shortest-path behavior (Kivimaki et al., 2014; Saerens et al., 2009; Yen et al., 2008). The framework assumes a unit flow injected into a source node and collected from a target node with flows minimizing the expected transportation cost, together with a relative entropy regularization term . In this context, the present work first develops the net flow RSP model considering that edge flows in opposite directions neutralize each other (as in electric networks), and proposes an algorithm for computing the expected routing costs between all pairs of nodes. This quantity is called the net flow RSP dissimilarity measure between nodes. Experimental comparisons on node clustering tasks indicate that the net flow RSP dissimilarity is competitive with other state-of-the-art dissimilarities. In the second part of the paper, it is shown how to introduce capacity constraints on edge flows, and a procedure is developed to solve this constrained problem by exploiting Lagrangian duality. These two extensions should improve significantly the scope of applications of the RSP framework.

Ecosystem functioning depends on multiple successful interactions, many supported by individual movements. The degree to which the landscape allows these interactions to take place has been referred to as ‘effective connectivity’ (EC). Many of the cumulative impacts of anthropogenic activities on ecosystem functioning arise from changes in EC. Therefore, a coherent framework to quantify EC is urgently needed. Recent theoretical developments propose that studying EC requires the simultaneous consideration of spatial, environmental and species intrinsic characteristics (SEI framework). In this paper we further expand the SEI framework by integrating advances in geographic information science, ecological niche modelling, movement ecology, island biogeography and network sciences to develop a comprehensive three-step methodological approach for quantifying EC. First, using niche modelling and movement ecology, we quantify the species movement probabilities with respect to local environmental conditions. Second, we quantify ecological distances between non-adjacent locations by integrating species movement responses to the local environment with the spatial configuration of the landscape using the expected cost obtained from the randomized shortest paths (RSP) framework. This expected cost generalizes the two most frequently used ecological distance metrics, i.e. least-cost distance and resistance distance. Moreover the ‘absorbing random walk’ properties of RSP allow the integration of new developments in connectivity research, i.e. spatial absorbing Markov chains, to account for movement-related mortality. Third, drawing from island biogeography and metapopulation ecology, we scale ecological distances by relevant speciesand area-specific parameters to estimate EC for the ecological process of interest, e.g. migration, dispersal or gene flow. The integrative and highly interdisciplinary approach we propose can lead to increasingly more realistic measures of EC at different organizational levels. Moreover efficient computation allows its application to large-scale high-resolution landscapes for theoretical studies, conservation planning and sustainable management of real landscapes. Circuitscape, movement cost, landscape resistance, least-cost distance, randomized shortest paths, resistance distance, SAMC, step selection function, survival

Increasingly precise spatial data (e.g. high-resolution imagery from remote sensing) allow for improved representations of the landscape network for assessing the combined effects of habitat loss and connectivity declines on biodiversity. However, evaluating large landscape networks presents a major computational challenge both in terms of working memory and computation time. We present the ConScape (i.e. “connected landscapes”) software library implemented in the high-performance open-source Julia language to compute metrics for connected habitat and movement flow on high-resolution landscapes. The combination of Julia's ‘just-in-time’ compiler, efficient algorithms and ‘landmarks’ to reduce the computational load allows ConScape to compute landscape ecological metrics—originally developed in metapopulation ecology (such as ‘metapopulation capacity’ and ‘probability of connectivity’)—for large landscapes. An additional major innovation in ConScape is the adoption of the randomized shortest paths framework to represent connectivity along the continuum from optimal to random movements, instead of only those extremes. We demonstrate ConScape's potential for using large datasets in sustainable land planning by modelling landscape connectivity based on remote-sensing data paired with GPS tracking of wild reindeer in Norway. To guide users, we discuss other applications, and provide a series of worked examples to showcase all ConScape's functionalities in Supplementary Material. Built by a team of ecologists, network scientists and software developers, ConScape is able to efficiently compute landscape metrics for high-resolution landscape representations to leverage the availability of large data for sustainable land use and biodiversity conservation. As a Julia implementation, ConScape combines computational efficiency with a transparent code base, which facilitates continued innovation through contributions from the rapidly growing community of landscape and connectivity modellers using Julia. circuitscape, conefor, ecological networks, least-cost path, metapopulation, random walk, randomized shortest paths

Following [21, 23], the present work investigates a new relative entropy-regularized algorithm for solving the optimal transport on a graph problem within the randomized shortest paths formalism. More precisely, a unit flow is injected into a set of input nodes and collected from a set of output nodes while minimizing the expected transportation cost together with a paths relative entropy regularization term, providing a randomized routing policy. The main advantage of this new formulation is the fact that it can easily accommodate edge flow capacity constraints which commonly occur in real-world problems. The resulting optimal routing policy, i.e., the probability distribution of following an edge in each node, is Markovian and is computed by constraining the input and output flows to the prescribed marginal probabilities thanks to a variant of the algorithm developed in [8]. In addition, experimental comparisons with other recently developed techniques show that the distance measure between nodes derived from the introduced model provides competitive results on semi-supervised classification tasks.

Human activities follow daily, weekly, and seasonal rhythms. The emergence of these rhythms is related to physiology and natural cycles as well as social constructs. The human body and its biological functions undergo near 24-h rhythms (circadian rhythms). While their frequencies are similar across people, their phases differ. In the chronobiology literature, people are categorized into morning-type, evening-type, and intermediate-type groups called chronotypes based on their tendency to sleep at different times of day. Typically, this typology builds on carefully designed questionnaires or manually crafted features of time series data on people's activity. Here, we introduce a method where time-stamped data from smartphones are decomposed into components using non-negative matrix factorization. The method does not require any predetermined assumptions about the typical times of sleep or activity: the results are fully context-dependent and determined by the most prominent features of the activity data. We demonstrate our method by applying it to a dataset of mobile phone screen usage logs of 400 university students, collected over a year. We find four emergent temporal components: morning activity, night activity, evening activity and activity at noon. Individual behavior can be reduced to weights on these four components. We do not observe any clear categories of people based on the weights, but individuals are rather placed on a continuous spectrum according to the timings of their phone activities. High weights for the morning and night components strongly correlate with sleep and wake-up times. Our work points towards a data-driven way of characterizing people based on their full daily and weekly rhythms of activity and behavior, instead of only focusing on the timing of their sleeping periods.

Randomized shortest paths (RSPs) are tool developed in recent years for different graph and network analysis applications, such as modelling movement or flow in networks. In essence, the RSP framework considers the temperature-dependent Gibbs–Boltzmann distribution over paths in the network. At low temperatures, the distribution focuses solely on the shortest or least-cost paths, while with increasing temperature, the distribution spreads over random walks on the network. Many relevant quantities can be computed conveniently from this distribution, and these often generalize traditional network measures in a sensible way. However, when modelling real phenomena with RSPs, one needs a principled way of estimating the parameters from data. In this work, we develop methods for computing the maximum likelihood estimate of the model parameters, with focus on the temperature parameter, when modelling phenomena based on movement, flow or spreading processes. We test the validity of the derived methods with trajectories generated on artificial networks as well as with real data on the movement of wild reindeer in a geographic landscape, used for estimating the degree of randomness in the movement of the animals. These examples demonstrate the attractiveness of the RSP framework as a generic model to be used in diverse applications. randomized shortest paths; random walk; shortest path; parameter estimation; maximum likelihood; animal movement modelling

This paper investigates a real-world application of the free energy distance between nodes of a graph [14, 20] by proposing an improved extension of the existing Fraud Detection System named APATE [36]. It relies on a new way of computing the free energy distance based on paths of increasing length, and scaling on large, sparse, graphs. This new approach is assessed on a real-world large-scale e-commerce payment transactions dataset obtained from a major Belgian credit card issuer. Our results show that the free-energy based approach reduces the computation time by one half while maintaining state-of-the art performance in term of Precision@100 on fraudulent card prediction.

The recently developed bag-of-paths (BoP) framework consists in setting a Gibbs-Boltzmann distribution on all feasible paths of a graph. This probability distribution favors short paths over long ones, with a free parameter (the temperature $T$) controlling the entropic level of the distribution. This formalism enables the computation of new distances or dissimilarities, interpolating between the shortest-path and the resistance distance, which have been shown to perform well in clustering and classification tasks. In this work, the bag-of-paths formalism is extended by adding two independent equality constraints fixing starting and ending nodes distributions of paths (margins). When the temperature is low, this formalism is shown to be equivalent to a relaxation of the optimal transport problem on a network where paths carry a flow between two discrete distributions on nodes. The randomization is achieved by considering free energy minimization instead of traditional cost minimization. Algorithms computing the optimal free energy solution are developed for two types of paths: hitting (or absorbing) paths and non-hitting, regular, paths, and require the inversion of an $n \times n$ matrix with $n$ being the number of nodes. Interestingly, for regular paths on an undirected graph, the resulting optimal policy interpolates between the deterministic optimal transport policy ($T \rightarrow 0^{+}$) and the solution to the corresponding electrical circuit ($T \rightarrow \infty$). Two distance measures between nodes and a dissimilarity between groups of nodes, both integrating weights on nodes, are derived from this framework., Comment: Preprint paper to appear in Network Science journal, Cambridge University Press

This work develops a generic framework, called the bag-of-paths (BoP), for link and network data analysis. The central idea is to assign a probability distribution on the set of all paths in a network. More precisely, a Gibbs-Boltzmann distribution is defined over a bag of paths in a network, that is, on a representation that considers all paths independently. We show that, under this distribution, the probability of drawing a path connecting two nodes can easily be computed in closed form by simple matrix inversion. This probability captures a notion of relatedness between nodes of the graph: two nodes are considered as highly related when they are connected by many, preferably low-cost, paths. As an application, two families of distances between nodes are derived from the BoP probabilities. Interestingly, the second distance family interpolates between the shortest path distance and the resistance distance. In addition, it extends the Bellman-Ford formula for computing the shortest path distance in order to integrate sub-optimal paths by simply replacing the minimum operator by the soft minimum operator. Experimental results on semi-supervised classification show that both of the new distance families are competitive with other state-of-the-art approaches. In addition to the distance measures studied in this paper, the bag-of-paths framework enables straightforward computation of many other relevant network measures., Comment: Manuscript submitted for publication

This paper introduces a novel and well-founded betweenness measure, called the bag-of-paths (BoP) betweenness, as well as its extension, the BoP group betweenness, to tackle semisupervised classification problems on weighted directed graphs. The objective of semisupervised classification is to assign a label to unlabeled nodes using the whole topology of the graph and the labeled nodes at our disposal. The BoP betweenness relies on a BoP framework, assigning a Boltzmann distribution on the set of all possible paths through the network such that long (high-cost) paths have a low probability of being picked from the bag, while short (low-cost) paths have a high probability of being picked. Within that context, the BoP betweenness of node $j$ is defined as the sum of the a posteriori probabilities that node $j$ lies in between two arbitrary nodes $(i,k)$ when picking a path starting in $i$ and ending in $k$ . Intuitively, a node typically receives a high betweenness if it has a large probability of appearing on paths connecting two arbitrary nodes of the network. This quantity can be computed in closed form by inverting an $n\times n$ matrix where $n$ is the number of nodes. For the group betweenness, the paths are constrained to start and end in nodes within the same class, thereby defining a within-class group betweenness for each class. Unlabeled nodes are then classified according to the class showing the highest group betweenness. Experiments on various real-world datasets show that the BoP group betweenness performs competitively compared to all the tested state-of-the-art methods. The benefit of the BoP betweenness is particularly noticeable when only a few labeled nodes are available.

This paper introduces two new closely related betweenness centrality measures based on the Randomized Shortest Paths (RSP) framework, which fill a gap between traditional network centrality measures based on shortest paths and more recent methods considering random walks or current flows. The framework defines Boltzmann probability distributions over paths of the network which focus on the shortest paths, but also take into account longer paths depending on an inverse temperature parameter. RSP's have previously proven to be useful in defining distance measures on networks. In this work we study their utility in quantifying the importance of the nodes of a network. The proposed RSP betweenness centralities combine, in an optimal way, the ideas of using the shortest and purely random paths for analysing the roles of network nodes, avoiding issues involving these two paradigms. We present the derivations of these measures and how they can be computed in an efficient way. In addition, we show with real world examples the potential of the RSP betweenness centralities in identifying interesting nodes of a network that more traditional methods might fail to notice., Comment: Minor updates; published in Scientific Reports

The loss, fragmentation and degradation of habitat everywhere on Earth prompts increasing attention to identifying landscape features that support animal movement (corridors) or impedes it (barriers). Most algorithms used to predict corridors assume that animals move through preferred habitat either optimally (e.g. least cost path) or as random walkers (e.g. current models), but neither extreme is realistic. We propose that corridors and barriers are two sides of the same coin and that animals experience landscapes as spatiotemporally dynamic corridor-barrier continua connecting (separating) functional areas where individuals fulfil specific ecological processes. Based on this conceptual framework, we propose a novel methodological approach that uses high-resolution individual-based movement data to predict corridor-barrier continua with increased realism. Our approach consists of two innovations. First, we use step selection functions (SSF) to predict friction maps quantifying corridor-barrier continua for tactical steps between consecutive locations. Secondly, we introduce to movement ecology the randomized shortest path algorithm (RSP) which operates on friction maps to predict the corridor-barrier continuum for strategic movements between functional areas. By modulating the parameter Ѳ, which controls the trade-off between exploration and optimal exploitation of the environment, RSP bridges the gap between algorithms assuming optimal movements (when Ѳ approaches infinity, RSP is equivalent to LCP) or random walk (when Ѳ → 0, RSP → current models). Using this approach, we identify migration corridors for GPS-monitored wild reindeer (Rangifer t. tarandus) in Norway. We demonstrate that reindeer movement is best predicted by an intermediate value of Ѳ, indicative of a movement trade-off between optimization and exploration. Model calibration allows identification of a corridor-barrier continuum that closely fits empirical data and demonstrates that RSP outperforms models that assume either optimality or random walk. The proposed approach models the multiscale cognitive maps by which animals likely navigate real landscapes and generalizes the most common algorithms for identifying corridors. Because suboptimal, but non-random, movement strategies are likely widespread, our approach has the potential to predict more realistic corridor-barrier continua for a wide range of species.

Although criticized for some of its limitations, modularity remains a standard measure for analyzing social networks. Quantifying the statistical surprise in the arrangement of the edges of the network has led to simple and powerful algorithms. However, relying solely on the distribution of edges instead of more complex structures such as paths limits the extent of modularity. Indeed, recent studies have shown restrictions of optimizing modularity, for instance its resolution limit. We introduce here a novel, formal and well-defined modularity measure based on random walks. We show how this modularity can be computed from paths induced by the graph instead of the traditionally used edges. We argue that by computing modularity on paths instead of edges, more informative features can be extracted from the network. We verify this hypothesis on a semi-supervised classification procedure of the nodes in the network, where we show that, under the same settings, the features of the random walk modularity help to classify better than the features of the usual modularity. Additionally, the proposed approach outperforms the classical label propagation procedure on two data sets of labeled social networks.

In document clustering, semantically similar documents are grouped together. The dimensionality of document collections is often very large, thousands or tens of thousands of terms. Thus, it is common to reduce the original dimensionality before clustering for computational reasons. Cosine distance is widely seen as the best choice for measuring the distances between documents in k-means clustering. In this paper, we experiment three dimensionality reduction methods with a selection of distance measures and show that after dimensionality reduction into small target dimensionalities, such as 10 or below, the superiority of cosine measure does not hold anymore. Also, for small dimensionalities, PCA dimensionality reduction method performs better than SVD. We also show how l 2 normalization affects different distance measures. The experiments are run for three document sets in English and one in Hindi.

Vertaisarvioitu. Lähtökohdat : Kansainvälisiäkään rekisteritutkimuksia lääkärien työajoista ei tiettävästi ole. Kyselytutkimusten mukaan lääkärien työajat ovat varsin pitkiä. Menetelmät : Tutkimme sairaalalääkärien toteutuneiden työaikojen vuositason muutoksia suhteessa kokoaikaisuuteen, ikään ja sukupuoleen. Aineistona oli 12 sairaanhoitopiirin työaikatiedot vuosilta 2014–2018 (n =13 543, 58 % naisia). Tulokset : Kokoaikaisiksi luokiteltujen lääkärien viikkotyöaika oli keskimäärin 43 tuntia. Yli neljäsosalla kokonaistyöaika vuodessa oli yli 2 000 tuntia. Selkeimpiä vuositason muutoksia työajoissa olivat alle 13 tunnin päivystysvuorojen osuuden kasvu yli 10 prosenttiyksiköllä 41 %:iin ja päivystys- ¬vuorojen määrän kasvu 4–5 vuorolla. Muutokset olivat samansuuntaisia naisilla ja miehillä, mutta miesten kokonaistyöaika oli keskimäärin noin 70 tuntia vuodessa pidempi kuin naisten. Päivystyksiä oli pääosin enemmän alle 35-vuotiailla, mutta vähintään viikon työvuorojaksoja ja vapaamuotoista päivystystä oli enemmän vanhemmilla lääkäreillä. Päätelmät : Sairaalalääkärien vuosina 2014–2018 toteutuneissa työajoissa näkyi varsin pitkä kokonaistyöaika ja alle 13 tunnin päivystysvuorojen osuuden kasvu. Lisää tutkimusta tarvitaan erikoisaloittain sekä uusien työaikasäännösten ja COVID-19-pandemian vaikutuksista työaikaan.