A quick MST‐based algorithm to obtain Pathfinder networks (∞, n − 1)

Arnaud Quirin, Oscar Cordón, Vicente P. Guerrero‐Bote, Benjamín Vargas‐Quesada and Felix Moya‐Anegón

Journal of the American Society for Information Science and Technology, 2008, vol. 59, issue 12, 1912-1924

Abstract: Network scaling algorithms such as the Pathfinder algorithm are used to prune many different kinds of networks, including citation networks, random networks, and social networks. However, this algorithm suffers from run time problems for large networks and online processing due to its O(n4) time complexity. In this article, we introduce a new alternative, the MST‐Pathfinder algorithm, which will allow us to prune the original network to get its PFNET(∞, n − 1) in just O(n2 · log n) time. The underlying idea comes from the fact that the union (superposition) of all the Minimum Spanning Trees extracted from a given network is equivalent to the PFNET resulting from the Pathfinder algorithm parameterized by a specific set of values (r = ∞ and q = n − 1), those usually considered in many different applications. Although this property is well‐known in the literature, it seems that no algorithm based on it has been proposed, up to now, to decrease the high computational cost of the original Pathfinder algorithm. We also present a mathematical proof of the correctness of this new alternative and test its good efficiency in two different case studies: one dedicated to the post‐processing of large random graphs, and the other one to a real world case in which medium networks obtained by a cocitation analysis of the scientific domains in different countries are pruned.

Date: 2008
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1002/asi.20904

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bla:jamist:v:59:y:2008:i:12:p:1912-1924

Ordering information: This journal article can be ordered from
https://doi.org/10.1002/(ISSN)1532-2890

Access Statistics for this article

More articles in Journal of the American Society for Information Science and Technology from Association for Information Science & Technology
Bibliographic data for series maintained by Wiley Content Delivery ().