Sorry, you need to enable JavaScript to visit this website.

Identifying sparse and dense sub-graphs in large graphs with a fast algorithm

TitoloIdentifying sparse and dense sub-graphs in large graphs with a fast algorithm
Tipo di pubblicazioneArticolo su Rivista peer-reviewed
Anno di Pubblicazione2014
AutoriFioriti, Vincenzo, and Chinnici M.
RivistaEPL
Volume108
ISSN02955075
Abstract

Identifying the nodes of small sub-graphs with no a priori information is a hard problem. In this work, we want to find each node of a sparse sub-graph embedded in both dynamic and static background graphs, of larger average degree. We show that by exploiting the summability over several background realizations of the Estrada-Benzi communicability and the Krylov approximation of the matrix exponential, it is possible to recover the sub-graph with a fast algorithm with computational complexity O ( Nn + Nn log( n)) in the worst case, where n is the number of nodes and N is the number of backgrounds. Relaxing the problem to complete sub-graphs, the same performance is obtained with a single background, with a best case complexity O (n). Copyright © EPLA, 2014.

Note

cited By 1

URLhttps://www.scopus.com/inward/record.uri?eid=2-s2.0-84918543695&doi=10.1209%2f0295-5075%2f108%2f50006&partnerID=40&md5=06dff6691d8c4f002c3ac6e8656279ff
DOI10.1209/0295-5075/108/50006
Citation KeyFioriti2014