CR-Graph: Community Reinforcement for Accurate Community Detection

Yoonsuk Kang; Jun Seok Lee; Won Yong Shin; Sang Wook Kim

doi:10.1145/3340531.3412145

CR-Graph: Community Reinforcement for Accurate Community Detection

Yoonsuk Kang, Jun Seok Lee, Won Yong Shin, Sang Wook Kim

Department of Computational Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Citations (Scopus)

Abstract

In this paper, we present CR-Graph (community reinforcement on graphs), a novel method that helps existing algorithms to perform more-accurate community detection (CD). Toward this end, CR-Graph strengthens the community structure of a given original graph by adding non-existent predicted intra-community edges and deleting existing predicted inter-community edges. To design CR-Graph, we propose the following two strategies: (1) predicting intra-community and inter-community edges (i.e., the type of edges) and (2) determining the amount of edges to be added/deleted. To show the effectiveness of CR-Graph, we conduct extensive experiments with various CD algorithms on 7 synthetic and 4 real-world graphs. The results demonstrate that CR-Graph improves the accuracy of all underlying CD algorithms universally and consistently.

Original language	English
Title of host publication	CIKM 2020 - Proceedings of the 29th ACM International Conference on Information and Knowledge Management
Publisher	Association for Computing Machinery
Pages	2077-2080
Number of pages	4
ISBN (Electronic)	9781450368599
DOIs	https://doi.org/10.1145/3340531.3412145
Publication status	Published - 2020 Oct 19
Event	29th ACM International Conference on Information and Knowledge Management, CIKM 2020 - Virtual, Online, Ireland Duration: 2020 Oct 19 → 2020 Oct 23

Publication series

Name	International Conference on Information and Knowledge Management, Proceedings

Conference

Conference	29th ACM International Conference on Information and Knowledge Management, CIKM 2020
Country/Territory	Ireland
City	Virtual, Online
Period	20/10/19 → 20/10/23

Bibliographical note

Funding Information:
This research was supported by (1) the National Research Foundation of Korea grant funded by the Korea government (NRF-2020R1A2B5B03001960), (2) the National Research Foundation of Korea grant funded by the Korea government (2018R1A5A7059549), and (3) the Next-Generation Information Computing Development Program through the National Research Foundation of Korea funded by the Ministry of Science, ICT (NRF-2017M3C4A7069440).

Publisher Copyright:
© 2020 ACM.

All Science Journal Classification (ASJC) codes

Business, Management and Accounting(all)
Decision Sciences(all)

Access to Document

10.1145/3340531.3412145

Cite this

Kang, Y., Lee, J. S., Shin, W. Y., & Kim, S. W. (2020). CR-Graph: Community Reinforcement for Accurate Community Detection. In CIKM 2020 - Proceedings of the 29th ACM International Conference on Information and Knowledge Management (pp. 2077-2080). (International Conference on Information and Knowledge Management, Proceedings). Association for Computing Machinery. https://doi.org/10.1145/3340531.3412145

@inproceedings{ac404498179640acb87e615ffddb3de5,

title = "CR-Graph: Community Reinforcement for Accurate Community Detection",

abstract = "In this paper, we present CR-Graph (community reinforcement on graphs), a novel method that helps existing algorithms to perform more-accurate community detection (CD). Toward this end, CR-Graph strengthens the community structure of a given original graph by adding non-existent predicted intra-community edges and deleting existing predicted inter-community edges. To design CR-Graph, we propose the following two strategies: (1) predicting intra-community and inter-community edges (i.e., the type of edges) and (2) determining the amount of edges to be added/deleted. To show the effectiveness of CR-Graph, we conduct extensive experiments with various CD algorithms on 7 synthetic and 4 real-world graphs. The results demonstrate that CR-Graph improves the accuracy of all underlying CD algorithms universally and consistently.",

author = "Yoonsuk Kang and Lee, {Jun Seok} and Shin, {Won Yong} and Kim, {Sang Wook}",

note = "Funding Information: This research was supported by (1) the National Research Foundation of Korea grant funded by the Korea government (NRF-2020R1A2B5B03001960), (2) the National Research Foundation of Korea grant funded by the Korea government (2018R1A5A7059549), and (3) the Next-Generation Information Computing Development Program through the National Research Foundation of Korea funded by the Ministry of Science, ICT (NRF-2017M3C4A7069440). Publisher Copyright: {\textcopyright} 2020 ACM.; 29th ACM International Conference on Information and Knowledge Management, CIKM 2020 ; Conference date: 19-10-2020 Through 23-10-2020",

year = "2020",

month = oct,

day = "19",

doi = "10.1145/3340531.3412145",

language = "English",

series = "International Conference on Information and Knowledge Management, Proceedings",

publisher = "Association for Computing Machinery",

pages = "2077--2080",

booktitle = "CIKM 2020 - Proceedings of the 29th ACM International Conference on Information and Knowledge Management",

}

Kang, Y, Lee, JS, Shin, WY & Kim, SW 2020, CR-Graph: Community Reinforcement for Accurate Community Detection. in CIKM 2020 - Proceedings of the 29th ACM International Conference on Information and Knowledge Management. International Conference on Information and Knowledge Management, Proceedings, Association for Computing Machinery, pp. 2077-2080, 29th ACM International Conference on Information and Knowledge Management, CIKM 2020, Virtual, Online, Ireland, 20/10/19. https://doi.org/10.1145/3340531.3412145

CR-Graph: Community Reinforcement for Accurate Community Detection. / Kang, Yoonsuk; Lee, Jun Seok; Shin, Won Yong et al.
CIKM 2020 - Proceedings of the 29th ACM International Conference on Information and Knowledge Management. Association for Computing Machinery, 2020. p. 2077-2080 (International Conference on Information and Knowledge Management, Proceedings).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - CR-Graph

T2 - 29th ACM International Conference on Information and Knowledge Management, CIKM 2020

AU - Kang, Yoonsuk

AU - Lee, Jun Seok

AU - Shin, Won Yong

AU - Kim, Sang Wook

N1 - Funding Information: This research was supported by (1) the National Research Foundation of Korea grant funded by the Korea government (NRF-2020R1A2B5B03001960), (2) the National Research Foundation of Korea grant funded by the Korea government (2018R1A5A7059549), and (3) the Next-Generation Information Computing Development Program through the National Research Foundation of Korea funded by the Ministry of Science, ICT (NRF-2017M3C4A7069440). Publisher Copyright: © 2020 ACM.

PY - 2020/10/19

Y1 - 2020/10/19

N2 - In this paper, we present CR-Graph (community reinforcement on graphs), a novel method that helps existing algorithms to perform more-accurate community detection (CD). Toward this end, CR-Graph strengthens the community structure of a given original graph by adding non-existent predicted intra-community edges and deleting existing predicted inter-community edges. To design CR-Graph, we propose the following two strategies: (1) predicting intra-community and inter-community edges (i.e., the type of edges) and (2) determining the amount of edges to be added/deleted. To show the effectiveness of CR-Graph, we conduct extensive experiments with various CD algorithms on 7 synthetic and 4 real-world graphs. The results demonstrate that CR-Graph improves the accuracy of all underlying CD algorithms universally and consistently.

AB - In this paper, we present CR-Graph (community reinforcement on graphs), a novel method that helps existing algorithms to perform more-accurate community detection (CD). Toward this end, CR-Graph strengthens the community structure of a given original graph by adding non-existent predicted intra-community edges and deleting existing predicted inter-community edges. To design CR-Graph, we propose the following two strategies: (1) predicting intra-community and inter-community edges (i.e., the type of edges) and (2) determining the amount of edges to be added/deleted. To show the effectiveness of CR-Graph, we conduct extensive experiments with various CD algorithms on 7 synthetic and 4 real-world graphs. The results demonstrate that CR-Graph improves the accuracy of all underlying CD algorithms universally and consistently.

UR - http://www.scopus.com/inward/record.url?scp=85095863158&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85095863158&partnerID=8YFLogxK

U2 - 10.1145/3340531.3412145

DO - 10.1145/3340531.3412145

M3 - Conference contribution

AN - SCOPUS:85095863158

T3 - International Conference on Information and Knowledge Management, Proceedings

SP - 2077

EP - 2080

BT - CIKM 2020 - Proceedings of the 29th ACM International Conference on Information and Knowledge Management

PB - Association for Computing Machinery

Y2 - 19 October 2020 through 23 October 2020

ER -

Kang Y, Lee JS, Shin WY, Kim SW. CR-Graph: Community Reinforcement for Accurate Community Detection. In CIKM 2020 - Proceedings of the 29th ACM International Conference on Information and Knowledge Management. Association for Computing Machinery. 2020. p. 2077-2080. (International Conference on Information and Knowledge Management, Proceedings). doi: 10.1145/3340531.3412145

CR-Graph: Community Reinforcement for Accurate Community Detection

Abstract

Publication series

Conference

Bibliographical note

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this