English   español  
Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/160916
logo share SHARE logo core CORE   Add this article to your Mendeley library MendeleyBASE

Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL
Exportar a otros formatos:


Mining k-reachable sets in real-world networks using domination in shortcut graphs

AuthorsChalupa, David; Blum, Christian
KeywordsShortcut graphs
Minimum dominating set
k-Reachable sets
Graph mining
Real-world networks
Issue Date2017
CitationJournal of Computational Science 22: 1- 14 (2017)
AbstractWe propose a technique for mining minimum sets with bounded reachability in real-world networks, i.e. the smallest vertex sets such that any other vertex is at distance at most k from at least one vertex of this set. Our technique uses a simple but efficient mechanism. We first introduce new edges to shorten the paths in our network to obtain a shortcut graph. As the next step, we search for the minimum dominating set in the shortcut graph. For this purpose, a variety of algorithmic approaches is applied and computationally studied. To the best of our knowledge, this approach and the impact of shortcut graph structure on the problem have not been systematically explored yet. Experimental results are presented for local samples of two social networks, as well as large network science graphs, including several research collaboration networks. Different profiles of k-reachable sets were found for different networks. We find that k-reachable set sizes sharply decline with increasing k and decreasing graph diameters in the context of shortcut graphs obtained from social networks, as well as the largest connected components of research collaboration networks. However, there are also real-world networks, which seem to have slightly different profiles. © 2017 Elsevier B.V.
Identifiersdoi: 10.1016/j.jocs.2017.07.012
issn: 1877-7503
Appears in Collections:(IIIA) Artículos
Files in This Item:
File Description SizeFormat 
accesoRestringido.pdf15,38 kBAdobe PDFThumbnail
Show full item record
Review this work

Related articles:

WARNING: Items in Digital.CSIC are protected by copyright, with all rights reserved, unless otherwise indicated.