Search

Considerable effort has been devoted to the study of network structures and connectivity patterns and their influence on network dynamics. A widely used assumption in network analysis models is that traffic follows the shortest paths connecting pairs of nonneighboring vertices. For example, graph centrality measures, community extraction algorithms, and core-periphery detection algorithms use this assumption. However, this is a very restricted perspective and can be misleading as a consequence of its focus on shortest path communications. In this work, we study the utilization of shortest paths in complex networks in different data dissemination scenarios. We also explore whether there are general properties that can make networks utilize shortest paths more effectively. By conducting simulations on a set of real-world and artificial networks, we show that the utilization of shortest paths in complex networks may not be as common as assumed. This implies that longer paths can be as important (in some cases) as the shortest paths. Our results show that at least two factors clearly influence shortest path utilization in a network: the structure of the network and the data dissemination algorithm. We also find that the type of a network is not a good indicator of its shortest path utilization.

In this paper we formally define the hierarchical clustering network problem (HCNP) as the problem to find a good hierarchical partition of a network. This new problem focuses on the dynamic process of the clustering rather than on the final picture of the clustering process. To address it, we introduce a new hierarchical clustering algorithm in networks, based on a new shortest path betweenness measure. To calculate it, the communication between each pair of nodes is weighed by the importance of the nodes that establish this communication. The weights or importance associated to each pair of nodes are calculated as the Shapley value of a game, named as the linear modularity game. This new measure, (the node-game shortest path betweenness measure), is used to obtain a hierarchical partition of the network by eliminating the link with the highest value. To evaluate the performance of our algorithm, we introduce several criteria that allow us to compare different dendrograms of a network from two point of view: modularity and homogeneity. Finally, we propose a faster algorithm based on a simplification of the node-game shortest path betweenness measure, whose order is quadratic on sparse networks. This fast version is competitive from a computational point of view with other hierarchical fast algorithms, and, in general, it provides better results.

Creating a routing backbone is a fundamental problem in both biology and engineering. The routing backbone of the trail networks of arboreal turtle ants (Cephalotes goniodontus) connects many nests and food sources using trail pheromone deposited by ants as they walk. Unlike species that forage on the ground, the trail networks of arboreal ants are constrained by the vegetation. We examined what objectives the trail networks meet by comparing the observed ant trail networks with networks of random, hypothetical trail networks in the same surrounding vegetation and with trails optimized for four objectives: minimizing path length, minimizing average edge length, minimizing number of nodes, and minimizing opportunities to get lost. The ants’ trails minimized path length by minimizing the number of nodes traversed rather than choosing short edges. In addition, the ants’ trails reduced the opportunity for ants to get lost at each node, favoring nodes with 3D configurations most likely to be reinforced by pheromone. Thus, rather than finding the shortest edges, turtle ant trail networks take advantage of natural variation in the environment to favor coherence, keeping the ants together on the trails., Author summary We investigated the trail networks of arboreal turtle ants in the canopy of the tropical forest, to ask what characterizes the colony’s choice of foraging paths within the vegetation. We monitored day to day changes in the junctions and edges of trail networks of colonies in the dry forest of western Mexico. We compared the paths used by the ants to simulated random paths in the surrounding vegetation. We found that the paths of turtle ants prioritize coherence, keeping ants together on the trail, over minimizing the average edge length. The choice of paths reduces the number of junctions in the trail where ants could get lost, and favors junctions with a physical configuration that makes it likely that successive ants will reinforce the same path. Our work suggests that design principles that emphasize keeping information flow constrained to streamlined, coherent trails may be useful in human-designed distributed routing and transport networks or robot swarms.

Energy efficiency in wireless sensor network [WSN] is the highly sorted area for the researchers. Number of protocols has been suggested for energy efficient information gathering for sensor networks. These protocols come under two broad categories called tree based approach and clustering techniques. In these techniques clustering is more suitable for real time applications and has much more scalability factor when compared with its previous counterpart. This paper presents the importance and factors affecting the clustering. Also this paper surveyed the different clustering algorithms with its extensions till date and proposed the clustering technique using Minimum Spanning Tree [MST] and shortest path concept with its strength and limitations.

This paper proposes a new network topology design method that considers all the road nodes, energy stations and load centers to ensure the distribution of pipes along the road. The traditional graph theory and Prim Minimum Spanning Tree (MST) are used to simplify the map and minimize the length of the pipeline. After analyzing the limitations of the traditional network topology model, Point-to-Point (PTP), we present a new model, Energy Station-to-Load Point (ESLP). The model is optimized by minimum cost, not the shortest path. Finally, Pipe Diameter Grading (PDG) is proposed based on ESLP by solving for the pipe diameter that gives the minimum cost under different load demands in the process of optimization. The network design method is effectively applied in a case, and the results show that the path of the optimized plan is 1.88% longer than that of the pre-optimized plan, but the cost is 2.38% lower. The sensitivity analysis shows that the cost of pipeline construction, project life and electricity price all have an impact on the optimization results, and the cost of pipeline construction is the most significant. The difference between the different classifications of pipelines affects whether PDG is effective or not.

In this paper, we highlight that Graph Theory is certainly well suited to an applications approach. One of the basic problems that this theory solves is finding the shortest path between two points. For this purpose, we propose two real-world problems aimed at STEM undergraduate students to be solved by using shortest path algorithms from Graph Theory after previous modeling.

Social Network Analysis is the use of Network and Graph Theory to study social phenomena, which was found to be highly relevant in areas like Criminology. This chapter provides an overview of key methods and tools that may be used for the analysis of criminal networks, which are presented in a real-world case study. Starting from available juridical acts, we have extracted data on the interactions among suspects within two Sicilian Mafia clans, obtaining two weighted undirected graphs. Then, we have investigated the roles of these weights on the criminal network's properties, focusing on two key features: weight distribution and shortest path length. We also present an experiment that aims to construct an artificial network that mirrors criminal behaviours. To this end, we have conducted a comparative degree distribution analysis between the real criminal networks, using some of the most popular artificial network models: Watts-Strogatz, Erd\H{o}s-R\'{e}nyi, and Barab\'{a}si-Albert, with some topology variations. This chapter will be a valuable tool for researchers who wish to employ social network analysis within their own area of interest., Comment: 13 pages, 4 figures. In: Data Science and Internet of Things. Springer, Cham. (2021)

The recent emerging advancements in the domain of the fuzzy sets are the framework of the T-spherical fuzzy set (TSFS) and interval valued T-spherical fuzzy set (IVTSFS). Keeping in view the promising significance of the latest research trend in the fuzzy sets and the enabling impact of IVTSFS, we proposed a novel framework for decision assembly using interval valued TSFS based upon encompassing the four impressive dimensions of human judgement including favor, abstinence, disfavor, and refusal degree. Another remarkable contribution is the optimization of information modeling and prevention of information loss by redefining the concept of each membership in interval. Moreover, the proposed research made a worthy contribution work by demonstrating the effective utilization of the interval valued TSFS based framework in anomaly detection, medical diagnosis, and shortest path problem. The proposed work demonstrates the effective remedial measure for the anomaly detection problem based on several parameters using the aggregation operators of IVTSFS. Moreover, the interval valued T-spherical fuzzy relations and their composition are illustrated to investigate the medical diagnosis problem. Furthermore, the notion of interval valued T-spherical fuzzy graph is also presented and fundamental notions of graph theory are also demonstrated with the help of real world instances. In the context of interval valued T-spherical fuzzy graphs (IVTSFGs), a modified Dijkstra Algorithm (DA) is developed and applied to the shortest path problem. The in-depth quantitative assessment and comparative analysis revealed that the proposed notion outpaces contemporary progressive approaches.

We consider the problem of building Distance Sensitivity Oracles (DSOs). Given a directed graph $G=(V, E)$ with edge weights in $\{1, 2, \dots, M\}$, we need to preprocess it into a data structure, and answer the following queries: given vertices $u,v\in V$ and a failed vertex or edge $f\in (V\cup E)$, output the length of the shortest path from $u$ to $v$ that does not go through $f$. Our main result is a simple DSO with $\tilde{O}(n^{2.7233}M)$ preprocessing time and $O(1)$ query time. Moreover, if the input graph is undirected, the preprocessing time can be improved to $\tilde{O}(n^{2.6865}M)$. The preprocessing algorithm is randomized with correct probability $\ge 1-1/n^C$, for a constant $C$ that can be made arbitrarily large. Previously, there is a DSO with $\tilde{O}(n^{2.8729}M)$ preprocessing time and $\operatorname{polylog}(n)$ query time [Chechik and Cohen, STOC'20]. At the core of our DSO is the following observation from [Bernstein and Karger, STOC'09]: if there is a DSO with preprocessing time $P$ and query time $Q$, then we can construct a DSO with preprocessing time $P+\tilde{O}(n^2)\cdot Q$ and query time $O(1)$. (Here $\tilde{O}(\cdot)$ hides $\operatorname{polylog}(n)$ factors.), Comment: journal version

pgRouting library provides functions to compute shortest path between any two points of a road network which is of great demand and also a topic of interest in the field of GIS, graph theory and transportation. To compute path in a road network, pgRouting functions process the entire road network which is a major bottleneck when it comes to routing in large road networks leading to the requirement of large server resources. A reduction/compression in the input network that is to be processed for path computation would improve the performance of pgRouting. In this study a map generalization based network model is proposed which extracts a significantly smaller subset of the road network aka skeleton which further used to divide the network into zones, that shall be selectively used in path computation. This results in processing a much smaller part of the network to compute path between any two points leading to an overall improvement in query performance of pgRouting when computing path, especially on large road networks. As part of assessment of this approach and its applicability to large road networks, the paper presents an in-depth analysis of the trade-offs between deviation in computed path and the performance gain in terms of space and time on road networks of varying sizes and topology to get a better understanding for both providing a sound proof of the utility of the proposed method and also to show its implementability within the current model of pgRouting or any other routing platforms.

International audience; This study is aimed at the application of the percolation theory to simulation of a sustainable network organization of the economy in conditions of high uncertainty of the external environment. The methods for investment and cost recovery efficiency calculation in order to achieve synergy are used in the course of networks formation. The methods of graph theory and one-dimensional percolation are used herein. The conceptual content of the modified percolation approach to the analysis and simulation of network structures is specified. The controlled process of network formation offers the possibility to form the percolation cluster on the basis of minimization of its length (the shortest path). The formation regularities of two types of a percolation cluster (internal and cross-border) as the basis for the creation of the appropriate network structures are revealed. The examples of the applied problems, which study the percolation based on lattice cells (lattice coupling problem), are considered herein. The results of empirical approbation of the proposed approach in the field of services with the description of the algorithm for the networks and a cluster formation are presented. The transition from the random Bernol's percolation (based on random selection of cells) in favor of the correlated percolation is justified.

The article deals with solving the scientific problem of select mining equipment for selection longwall faces of mining venture. The main goal of the paper is to study technology of coal extraction of mining venture. The paper proposes a new approach to solve a problem of mining equipment selection for longwall faces of mining venture. The article describes new method for selection of mining equipment based on theory graph. Special attention is given to technological aspects; they are lenght of longwall faces, depth of coal stratum. Predictions obtained for daily production of mining equipment are compared with design outputs. Conclusions regarding the main reason of instability of longwall faces workings are made. It is found that to be able to use standard algorithms find the shortest path between vertices, you must perform matrix description of the constructed graphs that illustrate the structure of the interaction of different types of control equipment. Using classical optimization of method of discrete mathematics and algorithms for finding the shortest path between two vertices of network models obtained from the formalization of graphs with maximum results of specific types of equipment production chains, solved the problem of rational choice cleaning equipment for the new site with the cost parameters of the mining equipment and cost of mining coal. The authors developed effective and appropriate variants for the mine development for different coal deposits of mining venture.

Graphs can be considered as useful mathematical models. Graph algorithms are a common part of undergraduate courses in discrete mathematics. Even though they have been successfully implemented in secondary curricula, little research has been dedicated to the analysis of students&rsquo, work. Within a discrete mathematics course for university students, several graph algorithms were introduced via their applications. At the end of the course, the students took a test focused, inter alia, on applications of the algorithms. The mistakes that occurred in 127 students&rsquo, solutions of three problems (the Chinese postman problem, the shortest path problem, and the minimum spanning tree problem) were categorized and compared. Surprisingly, no mistakes were identified in the mathematization of situations or in the interpretation of results with respect to the wording of the problem. The categories of errors varied regardless of the problem types. Hierarchical cluster analysis grouped together the students&rsquo, solutions for the Chinese postman problem and the minimum spanning tree problem. By means of nonparametric item response theory analysis, the Chinese postman problem was identified as the most problematic for students. Possible sources of this difficulty are discussed in more detail herein.

In this paper, we study the path planning for a cellular-connected unmanned aerial vehicle (UAV) to minimize its flying distance from given initial to final locations, while ensuring a target link quality in terms of the large-scale channel gain with each of its associated ground base stations (GBSs) during the flight. To this end, we propose the use of radio map that provides the information on the large-scale channel gains between each GBS and uniformly sampled locations on a three-dimensional (3D) grid over the region of interest, which are assumed to be time-invariant due to the generally static and large-size obstacles therein (e.g., buildings). Based on the given radio maps of the GBSs, we first obtain the optimal UAV path by solving an equivalent shortest path problem (SPP) in graph theory. To reduce the computation complexity of the optimal solution, we further propose a grid quantization method whereby the grid points in each GBS's radio map are more coarsely sampled by exploiting the spatial channel correlation over neighboring grids. Then, we solve the approximate SPP over the reduced-size radio map (graph) more efficiently. Numerical results show that the proposed solutions can effectively minimize the flying distance of the UAV subject to its communication quality constraint. Moreover, a flexible trade-off between performance and complexity can be achieved by adjusting the quantization ratio for the radio map., to appear in Proc. IEEE Global Communications Conference (Globecom), 2019

An efficient connectivity-based method for multi-objective optimisation applicable to the design of marine protected area networks is described. Multi-objective network optimisation highlighted previously unreported step changes in the structure of optimal subnetworks for protection associated with minimal changes in cost or benefit functions. This emphasises the desirability of performing a full, unconstrained, multi-objective optimisation for marine spatial planning. Brute force methods, examining all possible combinations of protected and unprotected sites for a network of sites, are impractical for all but the smallest networks as the number of possible networks grows as 2^m, where m is the number of sites within the network. A metaheuristic method based around Markov Chain Monte Carlo methods is described which searches for the set of Pareto optimal networks (or a good approximation thereto) given two separate objective functions, for example for network quality or effectiveness, population persistence, or cost of protection. The optimisation and search methods are independent of the choice of objective functions and can be easily extended to more than two functions. The speed, accuracy and convergence of the method under a range of network configurations are tested with model networks based on an extension of random geometric graphs. Examination of two real-world marine networks, one designated for the protection of the stony coral Lophelia pertusa, the other a hypothetical man-made network of oil and gas installations to protect hard substrate ecosystems, demonstrates the power of the method in finding multi-objective optimal solutions for networks of up to 100 sites. Results using network average shortest path as a proxy for population resilience and gene flow within the network supports the use of a conservation strategy based around highly connected clusters of sites.

We study how the graph structure of the Internet at the Autonomous Systems (AS) level evolved during a decade. For each year of the period 2008-2017 we consider a snapshot of the AS graph and examine how many features related to structure, connectivity and centrality changed over time. The analysis of these metrics provides topological and data traffic information and allows to clarify some assumptions about the models concerning the evolution of the Internet graph structure. We find that the size of the Internet roughly doubled. The overall trend of the average connectivity is an increase over time, while that of the shortest path length is a decrease over time. The internal core of the Internet is composed of a small fraction of big AS and is more stable and connected the external cores. A hierarchical organization emerges where a small fraction of big hubs are connected to many regions with high internal cohesiveness, poorly connected among them and containing AS with low and medium numbers of links. Centrality measurements indicate that the average number of shortest paths crossing an AS or containing a link between two of them decreased over time.

Graph theory is successfully applied in developing a relationship between chemical structure and biological activity. The relationship of two graph invariants, the eccentric connectivity index and the eccentric Zagreb index are investigated with regard to anti-inflammatory activity, for a dataset consisting of 76 pyrazole carboxylic acid hydrazide analogs. The eccentricity ε v of vertex v in a graph G is the distance between v and the vertex furthermost from v in a graph G. The distance between two vertices is the length of a shortest path between those vertices in a graph G. In this paper, we consider the Octagonal Grid O n m . We compute Connective Eccentric index C ξ ( G ) = ∑ v ∈ V ( G ) d v / ε v , Eccentric Connective Index ξ ( G ) = ∑ v ∈ V ( G ) d v ε v and eccentric Zagreb index of Octagonal Grid O n m , where d v represents the degree of the vertex v in G.

Among the main issues in the theory of geometric grids on spatial information systems, is the problem of finding the shortest path routing between two points. In this paper tried to using the graph theory and A* algorithms in transport management, the optimal method to find the shortest path with shortest time condition to be reviewed. In order to construct a graph that consists of a network of pathways and modelling of physical and phasing area, the shortest path routes, elected with the use of the algorithm is modified A*.At of the proposed method node selection Examining angle nodes the desired destination node and the next node is done. The advantage of this method is that due to the elimination of some routes, time of route calculation is reduced.

We investigated the influence of processing steps in the estimation of multivariate directed functional connectivity during seizures recorded with intracranial EEG (iEEG) on seizure-onset zone (SOZ) localization. We studied the effect of (i) the number of nodes, (ii) time-series normalization, (iii) the choice of multivariate time-varying connectivity measure: Adaptive Directed Transfer Function (ADTF) or Adaptive Partial Directed Coherence (APDC) and (iv) graph theory measure: outdegree or shortest path length. First, simulations were performed to quantify the influence of the various processing steps on the accuracy to localize the SOZ. Afterwards, the SOZ was estimated from a 113-electrodes iEEG seizure recording and compared with the resection that rendered the patient seizure-free. The simulations revealed that ADTF is preferred over APDC to localize the SOZ from ictal iEEG recordings. Normalizing the time series before analysis resulted in an increase of 25–35% of correctly localized SOZ, while adding more nodes to the connectivity analysis led to a moderate decrease of 10%, when comparing 128 with 32 input nodes. The real-seizure connectivity estimates localized the SOZ inside the resection area using the ADTF coupled to outdegree or shortest path length. Our study showed that normalizing the time-series is an important pre-processing step, while adding nodes to the analysis did only marginally affect the SOZ localization. The study shows that directed multivariate Granger-based connectivity analysis is feasible with many input nodes (> 100) and that normalization of the time-series before connectivity analysis is preferred. Electronic supplementary material The online version of this article (10.1007/s10548-018-0646-7) contains supplementary material, which is available to authorized users.

International audience; [Update 2021 - Corrigendum in Geomorphology] Statistical metrics can be used to analyse the morphology of natural or simulated karst systems; they allow describing, comparing, and quantifying their geometry and topology. In this paper, we present and discuss a set of such metrics. We study their properties and their usefulness based on a set of more than 30 karstic networks mapped by speleologists. The data set includes some of the largest explored cave systems in the world and represents a broad range of geological and speleogenetic conditions allowing us to test the proposed metrics, their variability, and their usefulness for the discrimination of different morphologies. All the proposed metrics require that the topographical survey of the caves are first converted to graphs consisting of vertices and edges. This data preprocessing includes several quality check operations and some corrections to ensure that the karst is represented as accurately as possible. The statistical parameters relating to the geometry of the system are then directly computed on the graphs, while the topological parameters are computed on a reduced version of the network focusing only on its structure. Among the tested metrics, we include some that were previously proposed such as tortuosity or the Howard's coefficients. We also investigate the possibility to use new metrics derived from graph theory. In total, 21 metrics are introduced, discussed in detail, and compared on the basis of our data set. This work shows that orientation analysis and, in particular, the entropy of the orientation data can help to detect the existence of inception features. The statistics on branch length are useful to describe the extension of the conduits within the network. Rather surprisingly, the tortuosity does not vary very significantly. It could be heavily influenced by the survey methodology. The degree of interconnectivity of the network, related to the presence of maze patterns, can be measured using different metrics such as the Howard's parameters, global cyclic coefficient, or the average vertex degree. The average vertex degree of the reduced graph proved to be the most useful as it is simple to compute, it discriminates properly the interconnected systems (mazes) from the acyclic ones (tree-like structures), and it permits us to classify the acyclic systems as a function of the total number of branches. This topological information is completed by three parameters, allowing us to refine the description. The correlation of vertex degree is rather simple to obtain. It is systematically negative on all studied data sets indicating a predominance of disassortative networks among karst systems. The average shortest path length is related to the transport efficiency. It is shown to be mainly correlated to the size of the network. Finally, central point dominance allows us to identify the presence of a centralized organization.

The shortest path problem is the problem of finding one-to-one path from the source to the destination. In real life, the problem involves conflicting and competing objectives, and many researchers solve the multiobjective shortest path optimization problem using a weighted linear combination of objectives. However, the solution of weighted sum is highly sensitive to the weights given, limiting the practicability of this method. Solving the problem by simultaneous optimization of the objective functions to generate a set of nondominated solutions can help to build a decision support system for travelers to choose their own path on the basis of their individual preferences. This chapter proposes a multiobjective mathematical model, solved using e-approach to obtain (heuristically) nondominated solutions of shortest paths with respect to time and distance. In this study, we consider minimizing both distance and time as the objective functions with real-life constraints such as time-dependent dynamic and deterministic travel times, time-dependent dynamic and deterministic waiting times, and time-dependent one-way traffic along the roads. We implement the proposed model by using the real-life planning data (1658 nodes and 4224 links) of Chennai city network (a metropolitan city in India with highly interconnected network of roads), and present the discussion on the multiobjective routing problem with real-life considerations.

Date of Conference: 12-15 Dec. 2016 Conference name: IEEE 16th International Conference on Data Mining Workshops (ICDMW), 2016 While research on time-varying graphs has attracted recent attention, the research community has limited or no access to real datasets to develop effective algorithms and systems. Using noisy and sparse GPS traces from vehicles, we develop a time-varying road network data set where edge weights differ over time. We present our methodology and share this dataset, along with a graph manipulation tool. We estimate the traffic conditions using the sparse GPS data available by characterizing the sparsity issues and assessing the properties of travel sequence data frequency domain. We develop interpolation methods to complete the sparse data into a complete graph dataset with realistic time-varying edge values. We evaluate the performance of time-varying and static shortest path solutions over the generated dynamic road network. The shortest paths using the dynamic graph produce very different results than the static version. We provide an independent Java API and a graph database to analyze and manipulate the generated time-varying graph data easily, not requiring any knowledge about the inners of the graph database system. We expect our solution to support researchers to pursue problems of time-varying graphs in terms of theoretical, algorithmic, and systems aspects. The data and Java API are available at: http://elif.eser.bilkent.edu.tr/roadnetwork. © 2016 IEEE.

International audience; The Minimum Eccentricity Shortest Path (MESP) Problem consists in determining a shortest path (a path whose length is the distance between its extremities) of minimum eccentricity in a graph. It was introduced by Dragan and Leitert [9] who described a linear-time algorithm which is an 8-approximation of the problem. In this paper, we study deeper the double-BFS procedure used in that algorithm and extend it to obtain a linear-time 3-approximation algorithm. We moreover study the link between the MESP problem and the notion of laminarity, introduced by Völkel et al [12], corresponding to its restriction to a diameter (i.e. a shortest path of maximum length), and show tight bounds between MESP and laminarity parameters.

Authors are in long term developing e-learning supports for some parts of Operation Research course. The original purpose was to prepare e-learning supports for students of FBE Mendelu, mainly for part-time form students, who have subscribed Economic mathematical methods course (EMM). Considering decreasing number of lessons on part-time form of study (16 hours in a semester, in comparison to 56 hours in full-time form of study), was for part-time form students even more difficult to fulfill exam requirements. As a help for students there was stage by stage prepared several of programs, they allow self-contained practicing of some linear programming methods. Programs did allow to users step-by-step verify their solution, i.e. whether their calculation are in accordance with algorithm described in lectures. Advantage for the students consists in fact, that each mistake (numerical or algorithmic) they were able to uncover, what contributes to increase of self-study effectiveness and from that resulting higher study motivation. Resulting from existing experience, authors decided to request for a new FRVS grant for academic year 2012, focused on e-learning support of selected graph theory problems. Within this project there was developed a tool allowing to make and according to the user needs interactively modify created graphs. On this graph it is possible individually, step by step (in compliance with on lectures presented algorithm) to practice solving of selected graph theory and network analysis problems (e.g. minimal spanning tree, shortest path in a graph, testing for cycles in a graph, critical path method etc.). Project is realized as modular and was realized in Delphi developing tool. Described algorithms are saved in dynamic linked libraries. There for it is very easy to add here new (newly programmed) algorithms. Project results (i.e. project experience obtained from e-learning supports) will be available for all FBE Mendelu members interested in this problematic.

The construction of large-scale, low-latency networks becomes difficult as the number of nodes increases. In general, the way to construct a theoretically optimal solution is unknown. However, it is known that some methods can construct suboptimal networks with low-latency. One such method is to construct large-scale networks from optimal or suboptimal small networks, using the product of graphs. There are two major advantages to this method. One is that we can reuse small, already known networks to construct large-scale networks. The other is that the networks obtained by this method have graphtheoretical symmetry, which reduces the overhead of communication between nodes. A network can be viewed as a "graph", which is a mathematical term from combinatorics. The design of low-latency networks can be treated as a mathematical problem of finding small diameter graphs with a given number of nodes ( called "order" ) and a given number of connections between each node ( called "degree" ). In this paper, we overview how to construct large graphs from optimal or suboptimal small graphs by using graph-theoretical products. We focus on the case of diameter 2 in particular. As an example, we introduce a graph of order 256, degree 22 and diameter 2, which granted us the Deepest Improvement Award at the "Graph Golf" competition. Moreover, the average shortest path length of the graph is the smallest in graphs of order 256 and degree 22.

In this paper, the road network of Akure (a city in south western Nigeria) was studied based on its shortest path properties. Three sections, each measuring 1 square mile, were sampled from the entire road network and developed into graphs using both a primal approach and graph theory in which the intersections and streets were represented as nodes and edges respectively. These graphs were assessed for the edge lengths and shortest paths between nodes from which their edge length distributions, average path lengths and efficiencies were also obtained. It was concluded that the city of Akure is self-organized with small world properties since the network case studies showed small path lengths.

International audience; Voronoi diagrams are fundamental data structures in computational geometry, with applications in such areas as physics-based simulations. For non-Euclidean distances, the Voronoi diagram must be performed over a grid-graph, where the edges encode the required distance information. Th e major bottleneck in this case is a shortest path algorithm that must be computed multiple times during the simulation. We present a GPU algorithm for solving the shortest path problem from multiple sources using a generalized distance function. Our algorithm was designed to leverage the grid-based nature of the underlying graph that represents the deformable objects. Experimental results report speed-ups up to 65× over a current reference sequential method.

Analysis of GPS traces shows that people often do not use the least cost path through the transportation network while making trips. This leads to the question which structural path characteristics can be used to construct realistic route choice sets for use in traffic simulation models. In this paper, we investigate the hypothesis that, for utilitarian trips, the route between origin and destination consists of a small number of concatenated least cost paths. The hypothesis is verified by analyzing routes extracted from large sets of recorded GPS traces which constitute revealed preference information. Trips have been extracted from the traces and for each trip the path in the transportation network is determined by map matching. This is followed by a path decomposition phase for which the algorithm constitutes the first contribution of this paper. There are multiple ways to split a given path in a directed graph into a minimal number of subpaths of minimal cost By calculating two specific path splittings, it is possible to identify subsets of the vertices (splitVertexSuites) that can be used to generate every possible minimum path splitting by taking one vertex from each such subset As a second contribution, we show how the extracted information is used in microscopic travel simulation. The distribution for the size of the minimum decomposition, extracted from the GPS traces, can be used in constrained enumeration methods for route choice set generation. The sets of vertices that can act as boundary vertices separating consecutive route parts contain way points (landmarks) having a particular meaning to their user. The paper explains the theoretical aspects of route splitting as well as the process to extract splitVertexSuites from big data. It reports statistical distributions extracted from sets of GPS traces for both multimodal person movements and unimodal car trips. The research leading to these results has received funding from the European Union Seventh Framework Programme (FP7/2007-2013) under grant agreement nr 270833.

A novel methodology to sectorize water supply networks (WSNs) depending on a main transmission line is presented in this paper. The methodology is based on concepts derived from the social network theory and graph theory (namely, community detection and shortest path respectively); and also on a multi-objective optimization process by means of agent swarm optimization (ASO). A series of energy, operative, and economic criteria are optimized in this process. The core idea is to form sectors over the distribution network based on communities found using a community detection algorithm (Walktrap). The methodology is flexible and enables the technical staff in water utilities to make decisions at different stages. It has been tested by generating four feasible solutions over a portion of a real WSN.

Recently, the number of studies involving complex network applications in transportation has increased steadily as scholars from various fields analyze traffic networks. Nonetheless, research on rail network growth is relatively rare. This research examines the evolution of the Public Urban Rail Transit Networks of Kuala Lumpur (PURTNoKL) based on complex network theory and covers both the topological structure of the rail system and future trends in network growth. In addition, network performance when facing different attack strategies is also assessed. Three topological network characteristics are considered: connections, clustering and centrality. In PURTNoKL, we found that the total number of nodes and edges exhibit a linear relationship and that the average degree stays within the interval [2.0488, 2.6774] with heavy-tailed distributions. The evolutionary process shows that the cumulative probability distribution (CPD) of degree and the average shortest path length show good fit with exponential distribution and normal distribution, respectively. Moreover, PURTNoKL exhibits clear cluster characteristics; most of the nodes have a 2-core value, and the CPDs of the centrality's closeness and betweenness follow a normal distribution function and an exponential distribution, respectively. Finally, we discuss four different types of network growth styles and the line extension process, which reveal that the rail network's growth is likely based on the nodes with the biggest lengths of the shortest path and that network protection should emphasize those nodes with the largest degrees and the highest betweenness values. This research may enhance the networkability of the rail system and better shape the future growth of public rail networks.

[EN] Graph theory solves, via a good modelization, a very large number of problems in different areas. This is why, this theory has been having an exponential increase in the last years. One of the basic problems that this theory solves is to obtain the shortest path between two points. In order to illustrate this problem, to motivate its study and to introduce the student in the world of the mathematical modelization and its large range of possibilities, we present a specific case: to help the police to catch the authors of a theft. The solution consists of representing the city where it took place by a no directed positive weighted graph and to apply the Floyd’s algorithm mixed with a reasoning of combinatorial type. At the end of the exercise, we can assure that the thieves cannot escape, by using another concept of graph theory, the vertex-cut., [ES] Numerosos problemas pertenecientes a los más diversos campos pueden ser resueltos a partir de la modelización en teoría de grafos, materia en pleno auge, podríamos decir que con crecimiento exponencial, por su amplia aplicabilidad. Uno de los primeros problemas que se plantean al alumno que inicia el estudio de la teoría de grafos es el cálculo del trazado de un camino de mínimo peso de un vértice a otro, es decir, el cálculo de la distancia mínima que separa dos vértices dados, así como el recorrido a realizar para obtenerla. Para ilustrarlo, motivar su estudio e iniciar al estudiante en el mundo de la modelización y su amplia gama de posibilidades, presentamos el siguiente caso concreto, en el que ayudamos a la policía a atrapar a los autores de un robo. La solución consiste en representar la ciudad en la que tiene lugar el atraco mediante un grafo no dirigido ponderado positivo, y aplicar el algoritmo de Floyd, entrelazado con razonamientos de tipo combinatorio. Podremos asegurar al final del ejercicio que los ladrones no tienen escapatoria, relacionando la solución con otro concepto de la teoría de grafos, la cortadura de vértices.

This paper presents new results for the modulus of families of walks on a graph---a discrete analog of the modulus of curve families due to Beurling and Ahlfors. Particular attention is paid to the dependence of the modulus on its parameters. Modulus is shown to generalize (and interpolate among) three important quantities in graph theory: shortest path, effective resistance, and max-flow or min-cut., Updated with referee's comments. To appear in ECGD

Cataloged from PDF version of article. Traffic management during an evacuation and the decision of where to locate the shelters are of critical importance to the performance of an evacuation plan. From the evacuation management authority’s point of view, the desirable goal is to minimize the total evacuation time by computing a system optimum (SO). However, evacuees may not be willing to take long routes enforced on them by a SO solution; but they may consent to taking routes with lengths not longer than the shortest path to the nearest shelter site by more than a tolerable factor. We develop a model that optimally locates shelters and assigns evacuees to the nearest shelter sites by assigning them to shortest paths, shortest and nearest with a given degree of tolerance, so that the total evacuation time is minimized. As the travel time on a road segment is often modeled as a nonlinear function of the flow on the segment, the resulting model is a nonlinear mixed integer programming model. We develop a solution method that can handle practical size problems using second order cone programming techniques. Using our model, we investigate the importance of the number and locations of shelter sites and the trade-off between efficiency and fairness. 2014 Elsevier Ltd. All rights reserved.

Censuses in Mexico are taken by the National Institute of Statistics and Geography (INEGI). In this paper a Two-Phase Approach (TPA) to optimize the routes of INEGI’s census takers is presented. For each pollster, in the first phase, a route is produced by means of the Simulated Annealing (SA) heuristic, which attempts to minimize the travel distance subject to particular constraints. Whenever the route is unrealizable, it is made realizable in the second phase by constructing a visibility graph for each obstacle and applying Dijkstra’s algorithm to determine the shortest path in this graph. A tuning methodology based on theiracepackage was used to determine the parameter values for TPA on a subset of 150 instances provided by INEGI. The practical effectiveness of TPA was assessed on another subset of 1962 instances, comparing its performance with that of the in-use heuristic (INEGIH). The results show that TPA clearly outperformsINEGIH. The average improvement is of 47.11%.

We consider the pricing problem of a risk-neutral monopolist who produces (at a cost) and offers an infinitely divisible good to a single potential buyer that can be of a finite number of (single dimensional) types. The buyer has a non-linear utility function that is differentiable, strictly concave and strictly increasing. Using a simple reformulation and shortest path problem duality as in Vohra (2011) we transform the initial non-convex pricing problem of the monopolist into an equivalent optimization problem yielding a closed-form pricing formula under a regularity assumption on the probability distribution of buyer types. We examine the solution of the problem when the regularity condition is relaxed in different ways, or when the production function is non-linear and convex. For arbitrary type distributions, we offer a complete solution procedure.

Intelligent mobile robotic agents demand optimal motion planners with minimal query time. Most contemporary algorithms lack one of these two required aspects. This paper proposes an efficient path-planning scheme based on cellular automata (CA) that generates optimal paths in the minimum time. A Cellular automaton is evolved over the entire search space and subsequently used for the determination of the shortest path. This approach generates a parent-child relationship for each cell in order to minimize the search time. Performance comparisons with A*, Dijkstra's, D* and MPCNN have proven it to be time-efficient. Analysis, simulation and experimental results have proven it to be a robust and complete path-planning scheme. Also it has demonstrated to be time-efficient in both static and dynamic environments.

Probabilistic analysis for metric optimization problems has mostly been conducted on random Euclidean instances, but little is known about metric instances drawn from distributions other than the Euclidean. This motivates our study of random metric instances for optimization problems obtained as follows: Every edge of a complete graph gets a weight drawn independently at random. The distance between two nodes is then the length of a shortest path (with respect to the weights drawn) that connects these nodes. We prove structural properties of the random shortest path metrics generated in this way. Our main structural contribution is the construction of a good clustering. Then we apply these findings to analyze the approximation ratios of heuristics for matching, the traveling salesman problem (TSP), and the k-median problem, as well as the running-time of the 2-opt heuristic for the TSP. The bounds that we obtain are considerably better than the respective worst-case bounds. This suggests that random shortest path metrics are easy instances, similar to random Euclidean instances, albeit for completely different structural reasons., To appear in Algorithmica

An Obstruction Avoidance Generously Mobility (OAGM) model has been introduced for controlling ad-hoc sensor networks and thereby operating emerging fields like military and healthcare services. According to this model, the ability to send a message to a group of users simultaneously, based solely on their geographic location, is desirable by using Mission Critical Mobility model that assumes the obstacle shapes like rectangle or square in the simulation terrain. The OAGM model is developed by grasping the critical situations of military and healthcare services by incorporating the node movement model, hierarchical node organization, placement of obstacle that affect the movement of nodes and also signal propagation. Graph theory technique is used to find the shortest path of the node movement process. The varying number of parameter sets with DSR protocol is analyzed for MCM and OAGM mobility model. The results show OAGM performance is better than MCM., 9 pages

To study the differences in functional brain networks between eyes-closed (EC) and eyes-open (EO) at resting state, electroencephalographic (EEG) activity was recorded in 21 normal adults during EC and EO states. The synchronization likelihood (SL) was applied to measure correlations between all pairwise EEG channels, and then the SL matrices were converted to graphs by thresholding. Graphs were measured by topological parameters in theta (4–7 Hz), alpha (8–13 Hz), and beta (14–30 Hz) bands. By changing from EC to EO states, mean cluster coefficients decreased in both theta and alpha bands, but mean shortest path lengths became shorter only in the alpha band. In addition, local efficiencies decreased in both theta and alpha bands, while global efficiencies in the alpha band increased inversely. Opening the eyes decreased both nodes and connections in frontal area in the theta band, and also decreased those in bilateral posterior areas in the alpha band. These results suggested that a combination of the SL and graph theory methods may be a useful tool for distinguishing states of EC and EO. The differences in functional connectivity between EC and EO states may reflect the difference of information communication in human brain.

Bootstrap methods have recently been introduced to diffusion-weighted magnetic resonance imaging to estimate the measurement uncertainty of ensuing diffusion parameters directly from the acquired data without the necessity to assume a noise model. These methods have been previously combined with deterministic streamline tractography algorithms to allow for the assessment of connection probabilities in the human brain. Thereby, the local noise induced disturbance in the diffusion data is accumulated additively due to the incremental progression of streamline tractography algorithms. Graph based approaches have been proposed to overcome this drawback of streamline techniques. For this reason, the bootstrap method is in the present work incorporated into a graph setup to derive a new probabilistic fiber tractography method, called BootGraph. The acquired data set is thereby converted into a weighted, undirected graph by defining a vertex in each voxel and edges between adjacent vertices. By means of the cone of uncertainty, which is derived using the wild bootstrap, a weight is thereafter assigned to each edge. Two path finding algorithms are subsequently applied to derive connection probabilities. While the first algorithm is based on the shortest path approach, the second algorithm takes all existing paths between two vertices into consideration. Tracking results are compared to an established algorithm based on the bootstrap method in combination with streamline fiber tractography and to another graph based algorithm. The BootGraph shows a very good performance in crossing situations with respect to false negatives and permits incorporating additional constraints, such as a curvature threshold. By inheriting the advantages of the bootstrap method and graph theory, the BootGraph method provides a computationally efficient and flexible probabilistic tractography setup to compute connection probability maps and virtual fiber pathways without the drawbacks of streamline tractography algorithms or the assumption of a noise distribution. Moreover, the BootGraph can be applied to common DTI data sets without further modifications and shows a high repeatability. Thus, it is very well suited for longitudinal studies and meta-studies based on DTI.