东华大学学报（英文版）2006，Vol.23Issue(6)：153-156,160,5.
An Efficient Algorithm for Discovering Co-occurrence Concepts Through Pathfinder Paradigm
An Efficient Algorithm for Discovering Co-occurrence Concepts Through Pathfinder Paradigm
DU Zhi-dian 1WANG James1
作者信息
- 1. School of Computing, Clemson University, SC USA 29634
- 折叠
摘要
Abstract
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.关键词
Pathfinder/CPFN/co-occurrenceKey words
Pathfinder/CPFN/co-occurrence分类
数理科学引用本文复制引用
DU Zhi-dian,WANG James..An Efficient Algorithm for Discovering Co-occurrence Concepts Through Pathfinder Paradigm[J].东华大学学报（英文版）,2006,23(6):153-156,160,5.
