Dense core model for cohesive subgraph discovery |
| |
| Institution: | 1. College of Mathematics and Information Science, Jiangxi Normal University, Nanchang, Jiangxi 330022, China;2. Faculty of Science, University of Kragujevac, P.O.Box 60, Kragujevac 34000, Serbia;3. State University of Novi Pazar, Novi Pazar, Serbia;1. Institute of Space and Astronautical Science JAXA, 3-1-1 Yoshinodai, Chuo-ku, Sagamihara, Kanagawa 252-5210, Japan;2. Department of Astronomy, Kyoto University, Kitashirakawa, Sakyo-ku, Kyoto 606-8502, Japan;3. Hiroshima Astrophysical Science Center, Hiroshima University, 1-3-1 Kagamiyama, Higashi-Hiroshima, Hiroshima 739-8526, Japan;4. Department of Physics, The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-0033, Japan |
| |
| Abstract: | Discovery of cohesive subgraphs is an important issue in social network analysis. As representative cohesive subgraphs, pseudo cliques have been developed by relaxing the perfection of cliques. By enumerating pseudo clique subgraphs, we can find some structures of interest such as a star-like structure. However, a little more complicated structures such as a core/periphery structure is still hard to be found by them. Therefore, we propose a novel pseudo clique called ρ-dense core and show the connection with the other pseudo cliques. Moreover, we show that a set of ρ-dense core subgraphs gives an optimal solution in a graph partitioning problem. Several experiments on real-life networks demonstrated the effectiveness for cohesive subgraph discovery. |
| |
| Keywords: | Graph analysis Pseudo clique Core/periphery structure |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
