Abstract: Community detection is a fundamental and widely-studied problem. Most existing community detection methods focus on network topology. However, with the proliferation of rich information available for entities in real-world networks, it is indispensable to capture the rich interaction between the structure and attributes in the graph for community detection. This paper proposes an Overlapping Community Detection method based on Colored random walk (OCDC). The algorithm is able to conquer the limitation of random walk-based community detection methods that directly utilize the original network topology. Specifically,  initial seed nodes in the network is firstly selected. Secondly, a seed replacement strategy is developed to capture a better-quality seed replacement path set. Thirdly, the structure-attribute interaction node transition matrix is generated to perform the colored random walk in order to obtain the colored distribution vector. Finally, based on the combination of structure and attri- bute, the parallel conductance is captured to expand the community. Experiments on synthetic networks and real-world network show that our proposed algorithm can accurately identify attributed communities and significantly outperform the state-of-the-art methods.

Key words: community detection, seed, colored random walk, parallel conductance