Search results for "Theoretical Computer Science"
showing 10 items of 1151 documents
Betweenness Centrality for Networks with Non-Overlapping Community Structure
2018
Evaluating the centrality of nodes in complex networks is one of the major research topics being explored due to its wide range of applications. Among the various measures that have been developed over the years, Betweenness centrality is one of the most popular. Indeed, it has proved to be efficient in many real-world situations. In this paper, we propose an extension of the Betweenness centrality designed for networks with nonoverlapping community structure. It is a linear combination of the so-called “local” and “global” Betweenness measures. The Local measure takes into account the influence of a node at the community level while the global measure depends only on the interactions betwe…
2020
Hierarchy and centrality are two popular notions used to characterize the importance of entities in complex systems. Indeed, many complex systems exhibit a natural hierarchical structure, and centrality is a fundamental characteristic allowing to identify key constituents. Several measures based on various aspects of network topology have been proposed in order to quantify these concepts. While numerous studies have investigated whether centrality measures convey redundant information, how centrality and hierarchy measures are related is still an open issue. In this paper, we investigate the association between centrality and hierarchy using several correlation and similarity evaluation mea…
Eventual Consistency Formalized
2019
Distribution of computation is well-known, and there are several frameworks, including some formal frameworks, that capture distributed computation. As yet, however, models of distributed computation are based on the idea that data is conceptually centralized. That is, they assume that data, even if it is distributed, is consistent. This assumption is not valid for many of the database systems in use today, where consistency is compromised to ensure availability and partition tolerance. Starting with an informal definition of eventual consistency, this paper explores several measures of inconsistency that quantify how far from consistency a system is. These measures capture key aspects of e…
Cimo: An efficient 2-phases calculator of multimodal itineraries for real trans-territories based on a dynamic programming
2015
In this work we propose an exact solution for calculating multimodal itinerary. This solution is named Cimo (Calculateur d'Itineraires Multimodaux Ordonnes). Cimo is an exact optimal itineraries' calculator wherein itineraries are sorted, multimodal, and trans-territorial. The solution is based on a dynamic programming algorithm "cut", "price" and "share". This solution is multi-objectives and multi-constraints. Several versions of this algorithm are proposed following a methodological approach that enables evaluation of efficiency and complexity's gain : through theoretical calculus and benchmarks. In the first version of realistic problem, we propose a solution with itineraries calculated…
Modelling of Systems for Real
2016
Modelling and Programming are often used together in system development. However, typically there is a large difference between the handling of modelling parts and the handling of programming parts. This leads to the fact that the transition between the two is not easy, and important information is lost as well as extra information has to be provided when combining modelling and programming. This paper shows how modelling and programming could work together in system development.
Retrieving Monitoring and Accounting Information from Constrained Devices in Internet-of-Things Applications
2013
Part 6: Monitoring Mechanisms; International audience; Internet-of-Things (IoT) is envisioned to provide connectivity to a vast number of sensing or actuating devices with limited computational and communication capabilities. For the organizations that manage these constrained devices, the monitoring of each device’s operational status and performance level as well as the accounting of their resource usage are of great importance. However, monitoring and accounting support is lacking in today’s IoT platforms. Hence, this paper studies the applicability of the Constrained Application Protocol (CoAP), a lightweight transfer protocol under development by IETF, for efficiently retrieving monito…
FMapper: Scalable read mapper based on succinct hash index on SunWay TaihuLight
2022
Abstract One of the most important application in bioinformatics is read mapping. With the rapidly increasing number of reads produced by next-generation sequencing (NGS) technology, there is a need for fast and efficient high-throughput read mappers. In this paper, we present FMapper – a highly scalable read mapper on the TaihuLight supercomputer optimized for its fourth-generation ShenWei many-core architecture (SW26010). In order to fully exploit the computational power of the SW26010, we employ dynamic scheduling of tasks, asynchronous I/O and data transfers and implement a vectorized version of the banded Myers algorithm tailored to the 256 bit vector registers of the SW26010. Our perf…
A low complexity distributed cluster based algorithm for spatial prediction
2017
Los mapas del entorno radioeléctrico (REM) pueden ser una herramienta esencial para numerosas aplicaciones en las futuras redes inalámbricas 5G. En este trabajo, empleamos un popular método geoestadístico llamado kriging ordinario para estimar el REM de un área cubierta por un eNodeB equipado con múltiples antenas. Los sensores inalámbricos se distribuyen por el área de interés y se organizan clústeres adaptativos de sensores para mejorar la calidad de la estimación del canal. En este trabajo, modificamos el algoritmo de clustering distribuido propuesto en un trabajo anterior para reducir la complejidad de la predicción de kriging. Se realizan simulaciones para detallar la técnica de formac…
Abel transforms with low regularity with applications to X-ray tomography on spherically symmetric manifolds
2017
We study ray transforms on spherically symmetric manifolds with a piecewise $C^{1,1}$ metric. Assuming the Herglotz condition, the X-ray transform is injective on the space of $L^2$ functions on such manifolds. We also prove injectivity results for broken ray transforms (with and without periodicity) on such manifolds with a $C^{1,1}$ metric. To make these problems tractable in low regularity, we introduce and study a class of generalized Abel transforms and study their properties. This low regularity setting is relevant for geophysical applications.
Automorphisms of hyperelliptic GAG-codes
2009
Abstract We determine the n –automorphism group of generalized algebraic-geometry codes associated with rational, elliptic and hyperelliptic function fields. Such group is, up to isomorphism, a subgroup of the automorphism group of the underlying function field.