Pathfinder Networks
Encyclopedia
Several psychometric scaling methods start from proximity 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 proximities for pairs of entities. Proximities can be obtained from similarities, correlations, distances, conditional probabilities, or any other measure of the relationships among entities. The entities are often concepts of some sort, but they can be anything with a pattern of relationships. 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. 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.
Here is an example of an undirected Pathfinder network derived from average similarity ratings of a group of biology graduate students. The students rated the similarity of all pairs of the terms shown.
Pathfinder uses two parameters. (1) The q parameter constrains the number of indirect proximities examined in generating the network. The q parameter is an integer value between 2 and n − 1, inclusive where n is the number of nodes or items. (2) The r parameter defines the metric used for computing the distance of paths (cf. the Minkowski distance
). The r parameter is a real number between 1 and infinity, inclusive. 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 = ∞, i.e., PFnet(n − 1, ∞).
With ordinal-scale data (see level of measurement
), the r-parameter should be infinity 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.
Essentially, Pathfinder networks preserve the shortest possible paths given the data so links are eliminated when they are not on shortest paths. The PFnet(n − 1, ∞) 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, ∞) includes all of the links in any minimum spanning tree.
Pathfinder networks are used in the study of expertise, knowledge acquisition, knowledge engineering, citation patterns, information retrieval, and data visualization. The networks are potentially applicable to any problem addressed by network theory
.
Data clustering
Cluster analysis or clustering is the task of assigning a set of objects into groups so that the objects in the same cluster are more similar to each other than to those in other clusters....
and multidimensional scaling
Multidimensional scaling
Multidimensional scaling is a set of related statistical techniques often used in information visualization for exploring similarities or dissimilarities in data. MDS is a special case of ordination. An MDS algorithm starts with a matrix of item–item similarities, then assigns a location to each...
are two such methods. Network scaling represents another method based on graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
. Pathfinder networks are derived from proximities for pairs of entities. Proximities can be obtained from similarities, correlations, distances, conditional probabilities, or any other measure of the relationships among entities. The entities are often concepts of some sort, but they can be anything with a pattern of relationships. 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. 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.
Here is an example of an undirected Pathfinder network derived from average similarity ratings of a group of biology graduate students. The students rated the similarity of all pairs of the terms shown.
Pathfinder uses two parameters. (1) The q parameter constrains the number of indirect proximities examined in generating the network. The q parameter is an integer value between 2 and n − 1, inclusive where n is the number of nodes or items. (2) The r parameter defines the metric used for computing the distance of paths (cf. the Minkowski distance
Minkowski distance
The Minkowski distance is a metric on Euclidean space which can be considered as a generalization of both the Euclidean distance and the Manhattan distance.-Definition:The Minkowski distance of order p between two pointsis defined as:...
). The r parameter is a real number between 1 and infinity, inclusive. 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 = ∞, i.e., PFnet(n − 1, ∞).
With ordinal-scale data (see level of measurement
Level of measurement
The "levels of measurement", or scales of measure are expressions that typically refer to the theory of scale types developed by the psychologist Stanley Smith Stevens. Stevens proposed his theory in a 1946 Science article titled "On the theory of scales of measurement"...
), the r-parameter should be infinity 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.
Essentially, Pathfinder networks preserve the shortest possible paths given the data so links are eliminated when they are not on shortest paths. The PFnet(n − 1, ∞) will be the minimum spanning tree
Minimum spanning tree
Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees...
for the links defined by the proximity data if a unique minimum spanning tree exists. In general, the PFnet(n − 1, ∞) includes all of the links in any minimum spanning tree.
Pathfinder networks are used in the study of expertise, knowledge acquisition, knowledge engineering, citation patterns, information retrieval, and data visualization. The networks are potentially applicable to any problem addressed by network theory
Network theory
Network theory is an area of computer science and network science and part of graph theory. It has application in many disciplines including statistical physics, particle physics, computer science, biology, economics, operations research, and sociology...
.