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(n4) 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.