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  刊 名： 東華大學(xué)學(xué)報(bào)（英文版）  EI 英文刊名： JOURNAL OF DONGHUA UNIVERSITY(ENGLISH EDITION)  年，卷(期)： 2006 23(6)  分類號(hào)： O1  關(guān)鍵詞： Pathfinder   CPFN   co-occurrence  

【An Efficient Algorithm for Discoveri】相關(guān)文章：

An Efficient Algorithm for Calculating Aircraft RCS Based on the Geometrical Characteristics04-28

BESⅢ track fitting algorithm04-28

Algorithm Design and Test of the Solar Guide Telescope04-28

An Efficient and Accurate Spectral Method for Acoustic Scattering in Elliptic Domains04-28

The New Enhanced Simple Authenticated Key Agreement Algorithm04-29

Underground water quality model inversion of genetic algorithm04-28

Internal circulating fluidized bed system and design algorithm04-29

A Minimum Cost Handover Algorithm for Mobile Satellite Networks04-28

Modified Frequency Scaling Algorithm for FMCW SAR Data Processing04-29

Genetic algorithm in DNA computing:A solution to the maximal clique problem04-30