Pathfinder network

Relationships among a set of elements are often represented as a square matrix with entries representing the relations between all pairs of the elements. Relations such as distances, dissimilarities, similarities, relatedness, correlations, co-occurrences, conditional probabilities, etc., can be represented by such matrices. Such data can also be represented as networks with weighted links between the elements. Such matrices and networks are extremely dense and are not easily apprehended without some form of data reduction or pruning.

A pathfinder network results from applying a pruning method that removes weaker links from a (usually dense) network according to the lengths of alternative paths (see below).

{{cite book

| year = 1990

| editor-last = Schvaneveldt

| editor-first = R.W.

| editor-link = Roger W. Schvaneveldt

| title = Pathfinder associative networks: Studies in knowledge organization

| place = Norwood, NJ

| publisher = Ablex

| isbn = 978-0893916244

| url = https://research-collective.com/PFWeb/docs/PFBook.zip

}}

{{Cite book

| last1 = Schvaneveldt

| first1 = R.W.

| author-link1 = Roger W. Schvaneveldt

| last2 = Durso

| first2 = F.T.

| last3 = Dearholt

| first3 = D.W.

| chapter = Network structures in proximity data

| year = 1989

| editor-last = Bower

| editor-first = G.

| title = The psychology of learning and motivation: Advances in research and theory

| volume = 24

| place = New York

| publisher = Academic Press

| pages = 249–284

| url = https://research-collective.com/PFWeb/Roger/Papers/Schvaneveldt_Durso_Dearholt_1989.pdf

}}

{{Cite journal

| last1 = Schvaneveldt

| first1 = R.W.

| author-link1 = Roger W. Schvaneveldt

| last3 = Durso

| first3 = F.T.

| last2 = Dearholt

| first2 = D.W.

| title = Graph theoretic foundations of Pathfinder Networks

| date = 1989

| journal = Computers and Mathematics with Applications

| volume = 15

| issue = 4

| pages = 337–345

| doi = 10.1016/0898-1221(88)90221-0

| url = https://research-collective.com/PFWeb/Roger/Papers/Schvaneveldt_Dearholt_Durso_1988.pdf

}} It is used as a psychometric scaling method based on graph theory and used in the study of expertise, education,{{Cite journal |last1=Goldsmith |first1=T. |last2=Johnson |first2=P. |last3=Acton |first3=W. |date=1991 |title=Assessing structural knowledge |journal=Journal of Educational Psychology |volume=83 |issue=4 |pages=88–96|doi=10.1037/0022-0663.83.1.88 }} knowledge acquisition, mental models,{{Cite journal |last1=Kudikyala |first1=U.K. |last2=Vaughn |first2=R.B. |date=2005 |title=Software requirement understanding using Pathfinder networks: discovering and evaluating mental models |url=https://doi.org/10.1016/j.jss.2003.09.028 |journal=Journal of Systems and Software |volume=74 |issue=1 |pages=101–108|doi=10.1016/j.jss.2003.09.028 }} and knowledge engineering. It is also employed in generating communication networks,{{Cite journal |last1=Shope |first1=S. M. |last2=DeJoode |first2=J. A. |last3=Cooke |first3=N. J. |last4=Pedersen |first4=H. |date=2004 |title=Using Pathfinder to Generate Communication Networks in a Cognitive Task Analysis |url=https://doi.org/10.1177/154193120404800386 |journal=Proceedings of the Human Factors and Ergonomics Society Annual Meeting |volume=48 |issue=3 |pages=678–682|doi=10.1177/154193120404800386 }} software debugging,{{Cite journal |last1=Serrano |first1=E. |last2=Quinn |first2=A. |last3=Botia |first3=J.A. |last4=Cordón |first4=O. |date=2010 |title=Debugging complex software systems by means of pathfinder networks. |journal=Information Science |volume=180 |issue=5 |pages=561–583|doi=10.1016/j.ins.2009.11.007 }} visualizing scientific citation patterns,{{Cite book |last1=Chen |first1=C. |title=Representing Scientific Knowledge |last2=Song |publisher=Springer |year=2017 |pages=57–137 |chapter=Science Mapping Tools and Applications.}} information retrieval, and other forms of data visualization.{{Cite journal |last=Cribbin |first=T. |date=2010 |title=Visualising the structure of document search results: A comparison of graph theoretic approaches |journal=Information Visualization |volume=9 |issue=2 |pages=83–97|doi=10.1057/ivs.2009.3 |url=http://bura.brunel.ac.uk/handle/2438/6701 }} Pathfinder networks are potentially applicable to any problem addressed by network theory.

Network pruning aims to highlight the more important links between elements represented in a network. It helps to simplify the collection of connections involved which is valuable in data visualization and in comprehending essential relations among the elements represented in the network.

Several psychometric scaling methods start from pairwise data and yield structures revealing the underlying organization of the data. Data clustering and multidimensional scaling are two such methods. Network scaling represents another method based on graph theory. Pathfinder networks are derived from matrices of data for pairs of entities. Because the algorithm uses distances, similarity data are inverted to yield dissimilarities for the computations.

In the pathfinder network, the entities correspond to the nodes of the generated network, and the links in the network are determined by the patterns of proximities. For example, if the proximities are similarities, links will generally connect nodes of high similarity. When proximities are distances or dissimilarities, links will connect the shorter distances. The links in the network will be undirected if the proximities are symmetrical for every pair of entities. Symmetrical proximities mean that the order of the entities is not important, so the proximity of i and j is the same as the proximity of j and i for all pairs i,j. If the proximities are not symmetrical for every pair, the links will be directed.

The pathfinder algorithm uses two parameters.

1. The $q$ parameter constrains the number of indirect proximities examined in generating the network. $q$ is an integer between $2$ and $n-1$, inclusive where $n$ is the number of nodes or items. Shortest paths can have no more than $q$ links. When $q\; =\; n\; -\; 1$, all possible paths are included.
2. The $r$ parameter defines the metric used for computing the distance of paths (cf. the Minkowski distance). $r$ is a real number between $1$ and $\backslash infin$, inclusive.

Path distance $d\_p$ is computed as: $d\_p\; =\; (\backslash sum\_\{i=\; 1\}^k\; l\_i^r)^\{1/r\}$, where $l\_i$ is the distance of the $i\; th$ link in the path and $2\; \backslash leq\; k\; \backslash leq\; q$. For $r\; =\; 1$, $d\_p$ is simply the sum of the distances of the links in the path. For $r\; =\; \backslash infin$, $d\_p$ is the maximum of the distances of the links in the path because $\backslash lim\_\{r\backslash rightarrow\backslash infin\}\; d\_p\; =\; \backslash max\_\{i=1\}^k\; l\_i$. A link is pruned if its distance is greater than the minimum distance of paths between the nodes connected by the link. Efficient methods for finding minimum distances include the Floyd–Warshall algorithm (for $q\; =\; n\; -\; 1$) and Dijkstra's algorithm (for any value of $q$).

A network generated with particular values of $q$ and $r$ is called a $PFNet(q,\; r)$. Both of the parameters have the effect of decreasing the number of links in the network as their values are increased. The network with the minimum number of links is obtained when $q\; =\; n\; -\; 1$ and $r\; =\; \backslash infin$, i.e., $PFNet(n\; -\; 1,\; \backslash infin)$.

With ordinal-scale data (see level of measurement), the $r$ parameter should be $\backslash infin$ because the same $PFNet$ would result from any positive monotonic transformation of the proximity data. Other values of $r$ require data measured on a ratio scale. The $q$ parameter can be varied to yield the desired number of links in the network or to focus on more local relations with smaller values of $q$.

Essentially, pathfinder networks preserve the shortest possible paths given the data. Therefore, links are eliminated when they are not on shortest paths. The $PFNet(n\; -\; 1,\; \backslash infin)$ will be the minimum spanning tree for the links defined by the proximity data if a unique minimum spanning tree exists. In general, the $PFNet(n\; -\; 1,\; \backslash infin)$ includes all of the links in any minimum spanning tree.

Here is an example of an undirected pathfinder network derived from average ratings of a group of biology graduate students. The students rated the relatedness of all pairs of the terms shown, and the mean rating for each pair was computed. The solid blue links are the $PFNet(n\; -\; 1,\; \backslash infin)$ (labeled "both" in the figure). The dotted red links are added in the $PFNet(2,\; \backslash infin)$. For the added links, there are no 2-link paths shorter than the link distance but there is at least one shorter path with more than two links in the data. A minimal spanning tree would have 24 links so the 26 links in $PFNet(n\; -\; 1,\; \backslash infin)$ implies that there is more than one minimum spanning tree. There are two cycles present so there are tied distances in the set of links in the cycle. Breaking each cycle would require removing one of the tied links in each cycle.

File:Bio2+.png

{{Reflist}}

Further information on pathfinder networks and several examples of the application of PFnets to a variety of problems can be found in the references.

• The 1990 book is out of print. A zipped copy of pdf chapters can be [https://research-collective.com/PFWeb/docs/PFBook.zip downloaded].

• The 1989 chapter in the Bower book is an article summarizing pathfinder networks and some applications. [https://research-collective.com/PFWeb/Roger/Papers/Schvaneveldt_Durso_Dearholt_1989.pdf pdf]

Three papers describing fast implementations of pathfinder networks:

• {{cite journal | doi = 10.1016/j.ipm.2006.03.015 | last1 = Guerrero-Bote | first1 = V. | last2 = Zapico-Alonso | first2 = F. | last3 = Esinosa-Calvo | first3 = M. | last4 = Gomez-Crisostomo | first4 = R. | last5 = Moya-Anegon | first5 = F. | year = 2006 | title = Binary pathfinder: An improvement to the pathfinder algorithm | journal = Information Processing and Management | volume = 42 | issue = 6| pages = 1484–1490 | citeseerx = 10.1.1.378.5375 }}
• {{cite journal | doi = 10.1016/j.ipm.2007.09.005 | last1 = Quirin | first1 = A | last2 = Cordón | first2 = O | last3 = Santamaría | first3 = J | last4 = Vargas-Quesada | first4 = B | last5 = Moya-Anegón | first5 = F | year = 2008 | title = A new variant of the Pathfinder algorithm to generate large visual science maps in cubic time | journal = Information Processing and Management | volume = 44 | issue = 4| pages = 1611–1623 }}
• {{cite journal | doi = 10.1002/asi.20904 | last1 = Quirin | first1 = A. | last2 = Cordón | first2 = O. | last3 = Guerrero-Bote | first3 = V. P. | last4 = Vargas-Quesada | first4 = B. | last5 = Moya-Anegón | first5 = F. | year = 2008 | title = A Quick MST-based Algorithm to Obtain Pathfinder Networks | journal = Journal of the American Society for Information Science and Technology | volume = 59 | issue = 12| pages = 1912–1924 | citeseerx = 10.1.1.331.1548 }}

(The two variants by Quirin et al. are significantly faster. While the former can be applied with $q\; =\; 2$ or $q\; =\; n-1$ and any value for $r$, the latter can only be applied in cases where $q\; =\; n\; -\; 1$ and $r\; =\; \backslash infin$.)

• [https://pfnets.net/Citations.html Extensive list of papers relating to Pathfinder]
• [https://pfnets.net/Download.html Pathfinder Software Download Site]
• [https://github.com/aquirin/pathfinder Implementation of the original, Binary, Fast and MST variants of the algorithm in C]
• [http://aquirin.fr/research/mstpathfinder.html Comparison table between the different variants]

Category:Psychometrics