A class of randomized Subset Selection Methods for large complex networks

Show simple item record

dc.contributor.author Reza, Amit
dc.contributor.author Tripathi, Richa
dc.date.accessioned 2019-06-19T11:12:57Z
dc.date.available 2019-06-19T11:12:57Z
dc.date.issued 2019-05
dc.identifier.citation Reza, Amit and Tripathi, Richa, "A class of randomized Subset Selection Methods for large complex networks", arXiv, Cornell University Library, DOI: arXiv:1905.04452, May 2019 en_US
dc.identifier.uri http://arxiv.org/abs/1905.04452
dc.identifier.uri https://repository.iitgn.ac.in/handle/123456789/4537
dc.description.abstract Most of the real world complex networks such as the Internet, World Wide Web and collaboration networks are huge; and to infer their structure and dynamics one requires handling large connectivity (adjacency) matrices. Also, to find out the spectra of these networks, one needs to perform the EigenValue Decomposition(or Singular Value Decomposition for bipartite networks) of these large adjacency matrices or their Laplacian matrices. In the present work, we proposed randomized versions of the existing heuristics to infer the norm and the spectrum of the adjacency matrices. In an earlier work [1], we used Subset Selection (SS) procedure to obtain the critical network structure which is smaller in size and retains the properties of original networks in terms of its Principal Singular Vector and eigenvalue spectra. We now present a few randomized versions of SS (RSS) and their time and space complexity calculation on various benchmark and real-world networks. We find that the RSS based on using QR decomposition instead of SVD in deterministic SS is the fastest. We evaluate the correctness and the performance speed after running these randomized SS heuristics on test networks and comparing the results with deterministic counterpart reported earlier. We find the proposed methods can be used effectively in large and sparse networks; they can be extended to analyse important network structure in dynamically evolving networks owing to their reduced time complexity.
dc.description.statementofresponsibility by Amit Reza and Richa Tripathi
dc.language.iso en en_US
dc.publisher Cornell University Library en_US
dc.title A class of randomized Subset Selection Methods for large complex networks en_US
dc.type Preprint en_US

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


My Account