Software
RelaxMap/GossipMap
[Parallel Flow-based Community Detection Algorithms]
Community-detection is a powerful approach to uncover important structures in large networks. Infomap is a flow-based and information-theoretic community detection algorithm. While Infomap is known to be an effective algorithm, it is critical to utilize parallel and distributed computing for taking care of huge graphs, such as web-scale graphs with billions of edges. In order to achieve high efficiency and output quality, we have developed a novel and efficient parallel generalization of Infomap, called RelaxMap, which is parallel flow-based community detection algorithm in shared-memory environments. In addition to RelaxMap, I extended the RelaxMap algorithm in distibuted-memory cluster systems for achieving high scalability, called GossipMap.
You can find source code and more detailed information for RelaxMap from HERE.
For the details of RelaxMap, please refer to our
ICDMW 2013 paper.
You can find source code for GossipMap from HERE.
For the details of GossipMap, please refer to our
SC 15 paper.
DA-MDS
[Solving MDS by using Deterministic Annealing Approach for Improving Maping Quality]
The Multidimensional Scaling (MDS) is known as a non-linear optimization problem so that it is easy to be trapped in local optima if EM-like hill-climbing approach is used to solve it. In order to avoid the local optima, we have applied the Deterministic Annealing (DA) method to the MDS problem.
You can find source code and more detailed information from HERE.
For the details of the proposed parallel DA-MDS algorithm (we call DA-SMACOF), please refer to the
eScience 2010 paper.
MI-MDS
[Majorizing Interpolation Approach of MDS for Large-Scale Data Visualization]
The idea of MDS interpolation method is two-step approach. As a preprocessing, we divide the given data set (total N points) into In-Sample data set, which has n points, and the remaining Out-of-Sample data set, which has N - n points. First, we run full MDS with In-Sample data set, and the points in the Out-of-Sample data set are mapped in the target dimension based on the mapping result of In-Sample data set via full MDS method. The interpolation method (we called MI-MDS) reduces the computational complexity from O(N2) to O(n(N-n)). It also reduces the memory requirement from O(N2) to O(n), since the proposed interpolation method finds a mapping for an interpolated point based on the mappings of In-Sample data points and the distances between the interpolated point and the points in In-Sample data set.
You can find more detailed information from HERE.
For the details of the proposed MDS interpolation method, please refer to our
HPDC 2010 paper.
HP-MDS
[MPI based High-Performance Parallel Implementation of MDS for Large-Scale Data Visualization]
Multidimensional Scaling (MDS) is an algorithm for constructing mappings of the given points in a target dimensional space based on pairwise proximity information. It is a computing and data intensive application, which requires O(N2) computation as well as memory. For the purpose of large-scale data visualization via MDS algorithm, we apply parallelization with Message Passing Interface (MPI) to increase computational capability by using distributed memory systems, i.e. multicore cluster systems.
You can find more detailed information from HERE.
For the details of the parallel MDS implementation, please refer to our
CCGrid 2010 paper.