Two Optimizations For Graphlet Random Walk Sampling Algorithm

A lot of applications are based on the characteristics of networks' local topology and graphlet belongs to one of these characters.A novel approach to identify a network is to sampling graphlets in the network and calculate the graphlet frequency distribution.The distribution can be applied to molecule network modeling,protein function analysis,internet topic tracking and emergency monitoring.When applying graphlet to study large scale networks,sampling processes are used to reduce the input size as it is computational expensive to generate graphlet frequency distribution.As current graphlet sampling methods do not utilize the multi-core feature of modern computers,we made improvement by designing parallel sampling methods which let multiple random walkers cooperate with each other.What's more,a proposed algorithm is used to eliminate the lack of convergence test.Finally,we improved code quality and optimized sampling strategy to reduce memory and time consumption when implementing the system.The experiments have shown that our newly proposed sampling method can produce unbiased result and the convergence analysis algorithm has the ability to indicate when the sampling process is converged.The parallel sampling methods can reduce 43% of the time cost at best,when the degree of parallelism is doubled.