Quirin, A; Cordon, O; Guerrero-Bote, VP; Vargas-Quesada, B; Moya-Anegon, F A quick MST-based algorithm to obtain Pathfinder networks (infinity, n-1) JOURNAL OF THE AMERICAN SOCIETY FOR INFORMATION SCIENCE AND TECHNOLOGY, 59 (12): 1912-1924 OCT 2008

[Eugene Garfield]

E-mail Address: arnaud.quirin at softcomputing.es; 
oscar.cordon at softcomputing.es; guerrero at unex.es; benjamin at ugr.es; 
felix at ugr.es 

Author(s): Quirin, A (Quirin, Arnaud); Cordon, O (Cordon, Oscar); Guerrero-
Bote, VP (Guerrero-Bote, Vicente P.); Vargas-Quesada, B (Vargas-Quesada, 
Benjamin); Moya-Anegon, F (Moya-Anegon, Felix) 

Title: A quick MST-based algorithm to obtain Pathfinder networks 
(infinity, n-1) 

Source: JOURNAL OF THE AMERICAN SOCIETY FOR INFORMATION SCIENCE AND 
TECHNOLOGY, 59 (12): 1912-1924 OCT 2008 

Language: English 

Document Type: Article 

Keywords Plus: SCIENCE; COCITATION; MAPS 

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(n(4)) 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(infinity, n - 1) in just O(n(2).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 = infinity 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. 

Addresses: [Quirin, Arnaud; Cordon, Oscar] European Ctr Soft Comp, Mieres, 
Spain; [Guerrero-Bote, Vicente P.] Univ Extremadura, Dept Informat & 
Commun, Badajoz, Spain; [Vargas-Quesada, Benjamin; Moya-Anegon, Felix] 
Univ Granada, SClmago Grp, Commun & Informat Sci Fac, Granada, Spain 

Reprint Address: Quirin, A, European Ctr Soft Comp, Edf Cientif Tecnol, 
Mieres, Spain. 

E-mail Address: arnaud.quirin at softcomputing.es; 
oscar.cordon at softcomputing.es; guerrero at unex.es; benjamin at ugr.es; 
felix at ugr.es 

Cited Reference Count: 31 

Times Cited: 0 

Publisher: JOHN WILEY & SONS INC 

Publisher Address: 111 RIVER ST, HOBOKEN, NJ 07030 USA 

ISSN: 1532-2882 

DOI: 10.1002/asi.20904 

29-char Source Abbrev.: J AM SOC INF SCI TECHNOL 

ISO Source Abbrev.: J. Am. Soc. Inf. Sci. Technol. 

Source Item Page Count: 13 

Subject Category: Computer Science, Information Systems; Information 
Science & Library Science 

ISI Document Delivery No.: 351WB 

BELLMAN R
DYNAMIC PROGR MOD CO : 1965

BORNER K
Network science 
ANNUAL REVIEW OF INFORMATION SCIENCE AND TECHNOLOGY 41 : 537 2007 

BREIGER RL
HDB DATA ANAL : 505 2004 

BUZYDLOWSKI J
THESIS DREXEL U : 2002 

CHEN C
INFORM VISUALIZATION : 2004 

CHEN C
P IEEE S INF VIS INF : 67 2003 

CHEN CM
Visualizing latent domain knowledge 
IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART C-APPLICATIONS AND 
REVIEWS 31 : 518 2001 

CHEN CM
Generalised similarity analysis and pathfinder network scaling 
INTERACTING WITH COMPUTERS 10 : 107 1998 

CHEN CM
Bridging the gap: The use of pathfinder networks in visual navigation 
JOURNAL OF VISUAL LANGUAGES AND COMPUTING 9 : 267 1998 

CORMEN TH
INTRO ALGORITHMS : 2001 

DEARHOLT DW
PATHFINDER ASS NETWO : 1 1990 

DEMOYAANEGON F
Domain analysis and information retrieval through the construction of 
heliocentric maps based on ISI-JCR category cocitation 
INFORMATION PROCESSING & MANAGEMENT 41 : 1520 DOI 
10.1016/j.ipm.2005.03.017 2005 

DEMOYAANEGON F
Visualizing the marrow of science 
JOURNAL OF THE AMERICAN SOCIETY FOR INFORMATION SCIENCE AND TECHNOLOGY 
58 : 2167 DOI 10.1002/asi.20683 2007
 
DREYFUS S
DYNAMIC PROGRAMMING : 1965 

FLOYD RW
ALGORITHM-97 - SHORTEST PATH
COMMUNICATIONS OF THE ACM 5 : 345 1962 

GANSNER ER
An open graph visualization system and its applications to software 
engineering 
SOFTWARE-PRACTICE & EXPERIENCE 30 : 1203 2000 

GUERREROBOTE VP
Binary Pathfinder: An improvement to the Pathfinder algorithm 
INFORMATION PROCESSING & MANAGEMENT 42 : 1484 DOI 
10.1016/j.ipm.2006.03.015 2006 

KAMADA T
AN ALGORITHM FOR DRAWING GENERAL UNDIRECTED GRAPHS 
INFORMATION PROCESSING LETTERS 31 : 7 1989 

KRAVITZ D
B ICA 49 : 7 2007 

KRUSKAL JB
P AM MATH SOC 7 : 48 1956 

KUDIKYALA UK
Software requirement understanding using Pathfinder networks: discovering 
and evaluating mental models 
JOURNAL OF SYSTEMS AND SOFTWARE 74 : 101 DOI 10.1016/j.jss.2003.09.028 
2005 

MARTINO F
PSYCHNOLOGY 4 : 53 2006 

MOYAANEGON F
A new technique for building maps of large scientific domains based on the 
cocitation of classes and categories 
SCIENTOMETRICS 61 : 129 2004 

PRIM RC
SHORTEST CONNECTION NETWORKS AND SOME GENERALIZATIONS
BELL SYSTEM TECHNICAL JOURNAL 36 : 1389 1957 

QUIRIN A
INFORM PROCESSING MA 44 : 1397 2008 

SALTON G
CITATION STUDY OF COMPUTER-SCIENCE LITERATURE
IEEE TRANSACTIONS ON PROFESSIONAL COMMUNICATION 22 : 146 1979 

SCHVANEVELDT RW
PATHFINDER ASS NETWO : 1990 

SHOPE SM
P HUMAN FACTORS ERGO : 678 2004 

SMALL H
THE GEOGRAPHY OF SCIENCE - DISCIPLINARY AND NATIONAL MAPPINGS 
JOURNAL OF INFORMATION SCIENCE 11 : 147 1985 

VARGAQUESADA B
VISUALIZING SCI STRU : 2007 

WARSHALL S
A THEOREM ON BOOLEAN MATRICES
JOURNAL OF THE ACM 9 : 11 1962