An Efficient Algorithm for Discovering Co-occurrence Concepts Through Pathfinder Paradigm
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.
作 者： DU Zhi-dian WANG James 作者单位： School of Computing, Clemson University, SC USA 29634 刊 名： 东华大学学报（英文版） EI 英文刊名： JOURNAL OF DONGHUA UNIVERSITY(ENGLISH EDITION) 年，卷(期)： 2006 23(6) 分类号： O1 关键词： Pathfinder CPFN co-occurrence