Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
3.7
2.3
Journals
Algorithms
Special Issues
Algorithmic Aspects of Networks
share announcement

Algorithmic Aspects of Networks

A special issue of Algorithms (ISSN 1999-4893). This special issue belongs to the section "Combinatorial Optimization, Graph, and Network Algorithms".

Deadline for manuscript submissions: closed (31 July 2020) | Viewed by 6644

Special Issue Editors

Prof. Dr. Pierluigi Crescenzi

E-Mail Website
Guest Editor
Gran Sasso Science Institute, Viale Francesco Crispi, 7, 67100 L'Aquila AQ, Italy
Interests: algorithms and complexity; approximation algorithms; complex network analysis
Assist. Prof. Dr. Andrea Marino

E-Mail Website
Guest Editor
Dipartimento di Informatica, Università di Pisa, Largo Bruno Pontecorvo 3, 56127 Pisa, Italy
Interests: algorithms and complexity; complex networks analysis; bioinformatics; enumeration algorithms
Special Issues, Collections and Topics in MDPI journals

Special Issue Information

Dear Colleagues,

Networks are everywhere, as they allow us to simply represent the relationships among things. The analysis of networks has hence attracted a lot of attention, since the very beginning of computer science. As the size of the real-world networks has been increasing very rapidly, designing efficient algorithms that are able to deal with this huge amount of data is a continuous and fascinating challenge. We invite you to submit your latest research in the area of the design, analysis, and experimental validation of efficient network algorithms to this Special Issue, “Algorithmic Aspects of Networks”. We are looking for new and innovative approaches for solving graph problems exactly or approximately, with emphasis on the problems arising in the field of real-world network analysis. High-quality papers are solicited to address both the theoretical and practical issues of network algorithms. Potential topics include, but are not limited to, centrality measures and network ranking, community detection, information diffusion, network clustering, network embedding, network pattern matching, and structural and topological network properties. The applicative scenarios in which these algorithms could be tested include, but are not limited to, bioinformatics, computer vision, machine learning, natural language processing, pattern analysis, robotics, and web and social network analytics, with emphasis on the applications that require the analysis of really huge networks.

Prof. Dr. Pierluigi Crescenzi
Prof. Dr. Andrea Marino
Guest Editors

Manuscript Submission Information

Manuscripts should be submitted online at www.mdpi.com by registering and logging in to this website. Once you are registered, click here to go to the submission form. Manuscripts can be submitted until the deadline. All submissions that pass pre-check are peer-reviewed. Accepted papers will be published continuously in the journal (as soon as accepted) and will be listed together on the special issue website. Research articles, review articles as well as short communications are invited. For planned papers, a title and short abstract (about 100 words) can be sent to the Editorial Office for announcement on this website.

Submitted manuscripts should not have been published previously, nor be under consideration for publication elsewhere (except conference proceedings papers). All manuscripts are thoroughly refereed through a single-blind peer-review process. A guide for authors and other relevant information for submission of manuscripts is available on the Instructions for Authors page. Algorithms is an international peer-reviewed open access monthly journal published by MDPI.

Please visit the Instructions for Authors page before submitting a manuscript. The Article Processing Charge (APC) for publication in this open access journal is 1600 CHF (Swiss Francs). Submitted papers should be well formatted and use good English. Authors may use MDPI's English editing service prior to publication or during author revisions.

Published Papers (2 papers)

Download All Papers
Order results
Result details
Show export options expand_more Show export options expand_less
Select all
Export citation of selected articles as:

Research

23 pages, 2563 KiB  
Article
Distributed Graph Diameter Approximation
by Matteo Ceccarello, Andrea Pietracaprina, Geppino Pucci and Eli Upfal
Algorithms 2020, 13(9), 216; https://0-doi-org.brum.beds.ac.uk/10.3390/a13090216 - 01 Sep 2020
Cited by 4 | Viewed by 3140
Abstract
We present an algorithm for approximating the diameter of massive weighted undirected graphs on distributed platforms supporting a MapReduce-like abstraction. In order to be efficient in terms of both time and space, our algorithm is based on a decomposition strategy which partitions the [...] Read more.
We present an algorithm for approximating the diameter of massive weighted undirected graphs on distributed platforms supporting a MapReduce-like abstraction. In order to be efficient in terms of both time and space, our algorithm is based on a decomposition strategy which partitions the graph into disjoint clusters of bounded radius. Theoretically, our algorithm uses linear space and yields a polylogarithmic approximation guarantee; most importantly, for a large family of graphs, it features a round complexity asymptotically smaller than the one exhibited by a natural approximation algorithm based on the state-of-the-art Δ-stepping SSSP algorithm, which is its only practical, linear-space competitor in the distributed setting. We complement our theoretical findings with a proof-of-concept experimental analysis on large benchmark graphs, which suggests that our algorithm may attain substantial improvements in terms of running time compared to the aforementioned competitor, while featuring, in practice, a similar approximation ratio. Full article
(This article belongs to the Special Issue Algorithmic Aspects of Networks)
►▼ Show Figures

Figure 1

30 pages, 743 KiB  
Article
Faster Algorithms for Mining Shortest-Path Distances from Massive Time-Evolving Graphs
by Mattia D’Emidio
Algorithms 2020, 13(8), 191; https://0-doi-org.brum.beds.ac.uk/10.3390/a13080191 - 04 Aug 2020
Cited by 4 | Viewed by 3190
Abstract
Computing shortest-path distances is a fundamental primitive in the context of graph data mining, since this kind of information is essential in a broad range of prominent applications, which include social network analysis, data routing, web search optimization, database design and route planning. [...] Read more.
Computing shortest-path distances is a fundamental primitive in the context of graph data mining, since this kind of information is essential in a broad range of prominent applications, which include social network analysis, data routing, web search optimization, database design and route planning. Standard algorithms for shortest paths (e.g., Dijkstra’s) do not scale well with the graph size, as they take more than a second or huge memory overheads to answer a single query on the distance for large-scale graph datasets. Hence, they are not suited to mine distances from big graphs, which are becoming the norm in most modern application contexts. Therefore, to achieve faster query answering, smarter and more scalable methods have been designed, the most effective of them based on precomputing and querying a compact representation of the transitive closure of the input graph, called the 2-hop-cover labeling. To use such approaches in realistic time-evolving scenarios, when the managed graph undergoes topological modifications over time, specific dynamic algorithms, carefully updating the labeling as the graph evolves, have been introduced. In fact, recomputing from scratch the 2-hop-cover structure every time the graph changes is not an option, as it induces unsustainable time overheads. While the state-of-the-art dynamic algorithm to update a 2-hop-cover labeling against incremental modifications (insertions of arcs/vertices, arc weights decreases) offers very fast update times, the only known solution for decremental modifications (deletions of arcs/vertices, arc weights increases) is still far from being considered practical, as it requires up to tens of seconds of processing per update in several prominent classes of real-world inputs, as experimentation shows. In this paper, we introduce a new dynamic algorithm to update 2-hop-cover labelings against decremental changes. We prove its correctness, formally analyze its worst-case performance, and assess its effectiveness through an experimental evaluation employing both real-world and synthetic inputs. Our results show that it improves, by up to several orders of magnitude, upon average update times of the only existing decremental algorithm, thus representing a step forward towards real-time distance mining in general, massive time-evolving graphs. Full article
(This article belongs to the Special Issue Algorithmic Aspects of Networks)
►▼ Show Figures

Figure 1

Show export options expand_more Show export options expand_less
Select all
Export citation of selected articles as:
 
Displaying articles 1-2
Back to TopTop