20 August 2019 in Networks and Spatial Economics
Advances in public transit modeling and smart card technologies can reveal detailed contact patterns of passengers. A natural way to represent such contact patterns is in the form of networks. In this paper we utilize known contact patterns from a public transit assignment model in a major metropolitan city, and propose the development of two novel network structures, each of which elucidate certain aspects of passenger travel behavior. We first propose the development of a transfer network, which can reveal passenger groups that travel together on a given day. Second, we propose the development of a community network, which is derived from the transfer network, and captures the similarity of travel patterns among passengers. We then explore the application of each of these network structures to identify the most frequently used travel paths, i.e., routes and transfers, in the public transit system, and model epidemic spreading risk among passengers of a public transit network, respectively. In the latter our conclusions reinforce previous observations, that routes crossing or connecting to the city center in the morning and afternoon peak hours are the most “dangerous” during an outbreak.
26 September 2018 in Annals of Computer Science and Information Systems
3 October 2021 in Social Network Analysis and Mining
Both community detection and influence maximization are well-researched fields of network science. Here, we investigate how several popular community detection algorithms can be used as part of a heuristic approach to influence maximization. The heuristic is based on the community value, a node-based metric defined on the outputs of overlapping community detection algorithms. This metric is used to select nodes as high influence candidates for expanding the set of influential nodes. Our aim in this paper is twofold. First, we evaluate the performance of eight frequently used overlapping community detection algorithms on this specific task to show how much improvement can be gained compared to the originally proposed method of Kempe et al. Second, selecting the community detection algorithm(s) with the best performance, we propose a variant of the influence maximization heuristic with significantly reduced runtime, at the cost of slightly reduced quality of the output. We use both artificial benchmarks and real-life networks to evaluate the performance of our approach.
19 August 2020 in Acta Cybernetica
In the last years personnel cost became a huge factor in the financial management of many companies and institutions.The firms are obligated to employ their workers in accordance with the law prescribing labour rules. The companies can save costs with minimizing the differences between the real and the expected worktimes. Crew rostering is assigning the workers to the previously determined shifts, which has been widely studied in the literature. In this paper, a mathematical model of the problem is presented and a two-phase graph coloring method for the crew rostering problem is introduced. Our method has been tested on artificially generated and real life input data. The results of the new algorithm have been compared to the solutions of the integer programming model for moderate-sized problems instances.