Visualizing network communities with a semi-definite programming method

• A novel method for visualizing networks, with the objective of highlighting community structures.
• A convex computational procedure, with guaranteed convergence and optimality.
• Improved visualization quality for real complex networks.
• Highly potential extension to other applications, including high dimensional data analysis.

The existence of community structures is commonly believed in complex networked systems and has gained significant research attention in recent years. The automatic detection of network communities poses a non-trivial challenge due to the inherent computational requirements. In this paper, we investigate the problem from a different perspective and propose a novel model to visualize networks with the objective of exposing their community structures based on the idea of modularity maximization. The model is relaxed by a simple convex positive semi-definite program, which can be optimized efficiently. Compared with other visualization approaches, through empirical evaluation our method is able to highlight network communities and the adversary vertices therein effectively. Thereby, it provides a useful tool in the family of community detection algorithms and in the family of graph layout methods.