경로파인더 네트워크

Pathfinder network
detail of a Tree of Knowledge after Diderot & d'Alembert's Encyclopédie, by Chrétien Frédéric Guillaume Roth
정보 매핑
주제 및 필드
노드 링크 접근 방식
참고 항목

경로파인더 네트워크는 그래프 이론을 바탕으로 한 사이코메트릭 스케일링 방식으로 전문성, 지식 습득, 지식 공학, 과학적 인용 패턴, 정보 검색, 데이터 시각화 연구에 사용된다.경로파인더 네트워크는 네트워크 이론에 의해 해결된 모든 문제에 잠재적으로 적용할 수 있다.

개요

몇 가지 사이코메트릭 스케일링 방법은 근접 데이터에서 시작되며 데이터의 기본 구성을 드러내는 구조를 산출한다.데이터 클러스터링과 다차원적 스케일링은 그러한 두 가지 방법이다.네트워크 스케일링은 그래프 이론에 기초한 또 다른 방법을 나타낸다.경로파인더 네트워크는 엔티티 쌍의 프록시로부터 파생된다.

대용치는 유사성, 상관성, 거리, 조건부 확률 또는 기업 간의 관계에 대한 다른 척도로 얻을 수 있다.실체는 종종 어떤 종류의 개념이지만, 그것들은 관계의 패턴이 있는 어떤 것이 될 수 있다.

경로파인더 네트워크에서, 실체는 생성된 네트워크의 노드에 대응하며, 네트워크의 링크는 프록시 패턴에 의해 결정된다.예를 들어, 근접성이 유사성인 경우 링크는 일반적으로 유사성이 높은 노드를 연결한다.네트워크의 링크는 근접성이 모든 엔티티 쌍에 대해 대칭인 경우 리디렉션되지 않는다.대칭 근위성은 실체의 순서가 중요하지 않다는 것을 의미하므로, 모든 쌍 i,j에 대해 i와 j의 근접성은 j와 i의 근접성과 동일하다.근접성이 모든 쌍에 대해 대칭적이지 않은 경우 링크가 지시된다.

예

생물학 대학원생 그룹의 평균 유사도 등급에서 도출된 비방향 경로파인더 네트워크의 예를 들어보자.학생들은 표시된 용어의 모든 쌍의 연관성을 평가했고 각 쌍의 평균 등급을 계산했다.표시된 네트워크는 PFnet(2, ∞)이다.

Bio q2.jpg

알고리즘.

경로파인더 알고리즘은 두 개의 파라미터를 사용한다.

  1. q 매개변수는 네트워크 생성에 있어 조사된 간접 대용물의 수를 제한한다.q 매개변수는 2와 n - 1 사이의 정수 값이며, 여기서 n은 노드 또는 항목의 수입니다.
  2. r 매개변수는 경로의 거리(cf. Minkowski 거리)를 계산하는 데 사용되는 메트릭을 정의한다.r 매개변수는 1과 무한대 사이의 실제 수입니다.

q와 r의 특정 값으로 생성되는 네트워크를 PFnet(q, r)이라고 한다.두 매개변수 모두 값이 증가함에 따라 네트워크의 링크 수를 감소시키는 효과가 있다.링크 수가 최소인 네트워크는 q = n - 1과 r = ∞, 즉 PFnet(n - 1, ∞)일 때 얻는다.

순서형 척도 데이터(측정 수준 참조)를 사용하는 경우, 동일한 PFnet이 근접 데이터의 양적인 단조적 변환에서 발생하므로 r-모수 변수는 무한대여야 한다.r의 다른 값에는 비율 척도로 측정된 데이터가 필요하다.q 매개변수는 네트워크에서 원하는 수의 링크를 산출하도록 변경될 수 있다.

기본적으로, 경로파인더 네트워크는 데이터가 주어진 가능한 최단 경로를 보존하기 때문에 최단 경로에 있지 않을 때 링크가 제거된다.고유한 최소 스패닝 트리가 존재하는 경우 PFnet(n - 1, ∞)은 근접 데이터에 의해 정의된 링크의 최소 스패닝 트리가 된다.일반적으로 PFnet(n - 1, ∞)은 최소 신장 트리의 모든 링크를 포함한다.

참조

경로파인더 네트워크에 대한 추가 정보와 다양한 문제에 대한 PFnet의 적용 예는 다음에서 찾을 수 있다.

  • Schvaneveldt, R. W. (Ed.) (1990) Pathfinder Associative Networks: Knowledge Organization의 연구.노우드, NJ: 캐블렉스.그 책은 절판되었다PDF 챕터의 압축 사본을 다운로드할 수 있음: zip

경로파인더 네트워크를 요약한 짧은 기사:

  • 슈반벨트, R. W., 더소, F. T., & 디어홀트, D. W. (1989년)근접 데이터의 네트워크 구조.G. 바워(Ed.)에서 학습과 동기부여의 심리학: 연구와 이론의 진보, 제24권 (pp. 249–284)뉴욕: 학술신문. pdf

경로파인더 네트워크의 빠른 구현에 대해 설명하는 세 가지 문서:

  • Guerrero-Bote, V.; Zapico-Alonso, F.; Esinosa-Calvo, M.; Gomez-Crisostomo, R.; Moya-Anegon, F. (2006). "Binary pathfinder: An improvement to the pathfinder algorithm". Information Processing and Management. 42 (6): 1484–1490. CiteSeerX 10.1.1.378.5375. doi:10.1016/j.ipm.2006.03.015.
  • Quirin, A; Cordón, O; Santamaría, J; Vargas-Quesada, B; Moya-Anegón, F (2008). "A new variant of the Pathfinder algorithm to generate large visual science maps in cubic time". Information Processing and Management. 44 (4): 1611–1623. doi:10.1016/j.ipm.2007.09.005.
  • Quirin, A.; Cordón, O.; Guerrero-Bote, V. P.; Vargas-Quesada, B.; Moya-Anegón, F. (2008). "A Quick MST-based Algorithm to Obtain Pathfinder Networks". Journal of the American Society for Information Science and Technology. 59 (12): 1912–1924. CiteSeerX 10.1.1.331.1548. doi:10.1002/asi.20904.

(Quirin 외 에 의한 두 변형은 현저하게 빠르다.전자는 q = 2 또는 q = n - 1과 r의 모든 값을 적용할 수 있지만, 후자는 q = n - 1과 r = ∞)의 경우에만 적용할 수 있다.

외부 링크