An Efficient Algorithm for Discovering Co-occurrence Concepts Through Pathfinder Paradigm

作     者：杜志典 WANG James 

作者机构：School of Computing Clemson University 

出 版 物：《Journal of Donghua University(English Edition)》 (东华大学学报（英文版）)

年 卷 期：2006年第23卷第6期

页      面：153-156,160页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081203[工学-计算机应用技术] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Pathfinder CPFN co-occurrence. 

摘      要：The Pathfinder paradigm has been used in generating and analyzing graph models that support clustering similar concepts and minimum-cost paths to provide an associative network structure within a domain. The co-occurrence pathfinder network （ CPFN ） extends the traditional pathfinder paradigm so that co-occurring concepts can be calculated at each sampling time. Existing algorithms take O（n（s）） time to calculate the pathfinder network （PFN） at each sampling time for a non-completed input graph of a CPFN （r = ∞, q = n - 1）, where n is the number of nodes in the input graph, r is the Minkowski exponent and q is the maximum number of links considered in finding a minimum cost path between vertices. To reduce the complexity of calculating the CPFN, we propose a greedy based algorithm, MEC（G） algorithm, which takes shortcuts to avoid unnecessary steps in the existing algorithms, to correctly calculate a CPFN （r = ∞, q= n - 1） in O（klogk） time where k is the number of edges of the input graph. Our example demonstrates the efficiency and correctness of the proposed MEC（G） algorithm, confirming our mathematic analysis on this algorithm.