์ด๋ฒ ํ๋ ์์ฝ
์ด๋ฒ์ฃผ์๋ Cytoscape.js์์ Measure์ ๋ํ ๊ธฐ๋ฅ์ ์ ๊ณตํ๋์ง ์์๋ณด๊ณ , ์ ์ ๊ณผ ๊ฐ์ ์ ์ถ๊ฐํ๊ณ ์ญ์ ํ ์ ์๋ ๊ธฐ๋ฅ์ ์ผ๋ถ ๊ตฌํํ๋ค.
Community Detection์ ์ด๋์ ๋ ๋์์ผ๋, ์ด์ ๋
ธ๋์ Degree, Path์ ๊ธธ์ด ๋ฑ Network์ ๋ํ ์ ๋ณด๋ฅผ ์ฌ์ฉ์์๊ฒ ์ ๊ณตํ๊ธฐ ์ํด์ Network๋ฅผ ์ธก์ ํ ์ ์๋ ๊ธฐ๋ฅ๋ค์ ์ ๊ณตํ๋์ง ์ฐพ์๋ณด์๋ค.
๊ธฐ์กด์๋ ํ์ด์ฌ์์ ํด๋น ๊ธฐ๋ฅ๋ค์ ์ ๊ณตํ๊ธฐ ๋๋ฌธ์ ํ์ด์ฌ์ ์ด๋ฏธ ๊ตฌํ์ด ๋์ด ์์ง๋ง, ํ๋ก ํธ๋จ์์ ๊ณ์ฐ์ ํด์ ๋ฐ๋ก ๋ณด์ฌ์ฃผ๊ฒ ๋๋ฉด ์๋ฌด๋๋ ๋ ๋น ๋ฅด๊ฒ ์ ๋ฌํ ์ ์๊ธฐ ๋๋ฌธ์ Cytoscape.js์์ ๊ทธ๋ฐ ๊ธฐ๋ฅ๋ค์ ์ ๊ณตํ๋์ง ์ฐพ์๋ณด์๋ค.
Network Analyzer
Cytoscape์์๋ Network์ ๋ํ ํต๊ณ ์ ๋ณด๋ฅผ ๋ด์ฃผ๋ Network Analyzer๋ผ๋ ๊ธฐ๋ฅ์ ์ ๊ณตํ๋ค.
์ฌ๊ธฐ์ ์ ๊ณตํ๋ ์ ๋ณด์๋ ์ฐ๋ฆฌ๊ฐ ํ์๋กํ๋ ์ ๋ณด๋ค์ด ๋๋ถ๋ถ ๋ค์ด์์๋ค.
๊ทธ๋์ ์ด๊ฑธ ์ฌ์ฉํ๋ฉด ๋๊ฒ ๊ฑฐ๋ ์๊ฐํ์ง๋ง, ์์ธ์ง Cytoscape ์ฑ์์๋ ์ ๊ณต์ ํ์ง๋ง, Cytoscape.js์์๋ ์ ๊ณตํ์ง ์๋ ๊ฒ ๊ฐ์๋ค.
์ด์ ๋๋ฉด ์ ๊ณตํ์ง ์๋ ๊ฒ์ด๋ผ ์๊ฐ์ด ๋ค ์ ๋๋ก ์์น๋ฅผ ํด๋ณด๊ธด ํ์ง๋ง ํ์ ์ ํ ์ ์์ผ๋, ์ผ๋จ์ ๊ธฐ์กด๋๋ก ํ์ด์ฌ ์ฝ๋๋ฅผ ์ฌ์ฉํ๊ณ ๋์ค์ ์ฐพ๊ฒ๋๋ฉด ๊ต์ฒด๋ฅผ ํ๊ธฐ๋ก ํ๋ค.
์๋ก์ด ๊ธฐ๋ฅ ๊ตฌํ
์ง๋๋ฒ์๋ ์ต์ ์ ๋ํ ๋ ์ด์์๋ง ์์ฑํ๊ณ , ๊ธฐ๋ฅ์ ๋ฃ์ง ์์์ง๋ง ์ด๋ฒ์๋ ์ค์ ๊ธฐ๋ฅ์ ์ฌ์ฉํ ์์๋๋ก ๊ตฌํ์ ํ๋ค.
์ด๋ฒ์๋ ํฌ๊ฒ 2๊ฐ์ง์ ๊ธฐ๋ฅ์ ๊ตฌํํ๋ค.
1. ์๋ก์ด ์ ์ , ๊ฐ์ ์์ฑ
: ์๋ก์ด ์ ์ , ๊ฐ์ ์ ์์ฑํ๊ณ ์ค์๊ฐ์ผ๋ก ํ์ธํ ์ ์๋ค.
์๋ก์ด ๊ฐ์ ์ด ์ถ๊ฐ๋๋ ๊ฒฝ์ฐ, ํด๋น ๊ฐ์ ์ผ๋ก ์ธํด ๋ ์ปค๋ฎค๋ํฐ๊ฐ ํ๋๋ก ํฉ์ณ์ง๊ฒ ๋๋ฉด ํ๋์ ์์์ผ๋ก ์น ํด์ง๋๋ก ํ๋ ค๊ณ ํ์ง๋ง ์ด๋ฒ์๋ ์คํจํ๋ค.
2. ์ ์ ์ญ์
: ํน์ ํค์๋๋ฅผ ํฌํจํ๋ ์ ์ ์ ์ญ์ ํ๊ณ , ํด๋น ์ ์ ๊ณผ ์ฐ๊ฒฐ๋ ๊ฐ์ ๋ค๋ ๋ชจ๋ ์ญ์ ํ๋ค.
ํผ๋๋ฐฑ
์ง๊ธ๊น์ง์ ๊ตฌํ์ ๋ฐํ์ผ๋ก ๊ต์๋์ด ํผ๋๋ฐฑ์ ์ฃผ์ จ๋ค.
1. ๊ฐ์ ๋ ์ญ์ ๋ฅผ ํ ์ ์์ผ๋ฉด ์ข๊ฒ ๋ค.
ํน์ ์ ์ ์ ์ปค๋ฎค๋ํฐ์์ ๋ถ๋ฆฌํ๊ณ ์ถ์ ๊ฒฝ์ฐ๊ฐ ์์ ์ ์๊ธฐ ๋๋ฌธ์ ๋
ธ๋ ๋ฟ ์๋๋ผ ๊ฐ์ ๋ ์ญ์ ๊ฐ ๊ฐ๋ฅํ๋ฉด ์ข๊ฒ ๋ค๊ณ ํ์
จ๋ค.
2. ์ ์ , ๊ฐ์ ์ ์ญ์ ํ ๋ ์
๋ ฅ ๋ฟ ์๋๋ผ, ํด๋ฆญ์ผ๋ก ์ญ์ ํ ์ ์์ผ๋ฉด ์ข๊ฒ ๋ค.
ํ์ฌ ๊ตฌํ๋ ๊ธฐ๋ฅ์ ์ ์ ์ ๋ถ์ ๋ผ๋ฒจ์ ์
๋ ฅํ๋ฉด ํด๋น ์ ์ ์ ์ฐพ์์ ์ญ์ ํ๋๋ก ๋์ด ์๋๋ฐ, ์ญ์ ํ๊ณ ์ ํ๋ ๋
ธ๋๋ฅผ ํด๋ฆญํด์ ์ญ์ ํ ์ ์๋ค๋ฉด ๋ ํธ๋ฆฌํ ๊ฒ ๊ฐ๋ค.
์ด๊ฑด ํด๋ฆญ์ด๋ฒคํธ๊ฐ ๋ฐ์ํ ์ ์ ์ ID ๊ฐ๋ง ์์๋ผ ์ ์๋ค๋ฉด ์ถฉ๋ถํ ํ ์ ์์ ๊ฒ ๊ฐ๋ค.
3. ์ ์ ์ ์ญ์ ํ ๋, ๊ฐ์ ์ผ๋ก ์ฐ๊ฒฐ๋ ์ด์ํ ๋
ธ๋๋ค๋ ๊ฐ์ด ์ง์์ง๋๋ฐ ์ด๊ฑธ ์ ํํ ์ ์์ผ๋ฉด ์ข๊ฒ ๋ค.
์ง๊ธ์ ํน์ ์ ์ ์ด ์ญ์ ๋๋ฉด, ํด๋น ์ ์ ์ ์ฐ๊ฒฐ๋ ๊ฐ์ ๊ณผ ์ ์ ์ ๋ชจ๋ ์ญ์ ํ๊ณ ์๋ค.
๊ทธ๋ฐ๋ฐ ๊ฐ์ ๊น์ง๋ ์ ๊ฑฐํด๋ ๋ฐ๋ํธ์ ์๋ ์ ์ ์ ์ด๋ ค๋ ์๋ ์๊ฒ ํ์ผ๋ฉด ์ข๊ฒ ๋ค๊ณ ํ์
จ๋ค.
๋ ผ์ ์ฌํญ
์งํํ๋ฉด์ ๊ถ๊ธํ๋ ๋ด์ฉ์ด๋ ๋ ผ์๊ฐ ํ์ํ ๋ด์ฉ๋ค
1. ๊ธฐ์กด ์ต์
์ ๋ํ ์ดํด
๊ธฐ์กด์ ์๋ ํ์ด์ง๋ฅผ ํ์ฌ ๊ตฌํ์ค์ธ ํ์ด์ง์์ ์จ์ ํ ๊ธฐ๋ฅํ ์ ์๋๋ก ํ๊ธฐ ์ํด์๋, ๊ธฐ์กด์ ์๋ ์ต์
๋ค์ด ์ ํํ ์ด๋ค ๊ธฐ๋ฅ๋ค์ ํ๋์ง ์ดํด๊ฐ ํ์ํ๋ค๊ณ ์๊ฐํ๋ค.
2. ์๋ฒ ๊ตฌ์ถ
๊ทธ๋ํ์ ์ฌ์ฉ๋๋ ๋ฐ์ดํฐ๋ฅผ ์ ๊ณตํ๋ ์๋ฒ๋ฅผ ๋ฌ์ผ ํ๋๋ฐ, ์ฐ๊ตฌ์ค์ ์๋ ์๋ฒ ์ปดํจํฐ์ ์ฐ๋ฆฌ์ ์๋ฒ๋ฅผ ์ด๋ค ์์ผ๋ก ๊ตฌ์ถํ ๊ฒ์ธ์ง ๋
ผ์๊ฐ ํ์ํ๋ค.
์ฑ๋ฅ์ด ์ข์ ์๋ฒ ์ปดํจํฐ๊ฐ ์๊ธฐ ๋๋ฌธ์ ๊ตณ์ด ๋น์ฉ์ด ๋ฐ์ํ๋ ํด๋ผ์ฐ๋๋ฅผ ์ฌ์ฉํ์ง ์์๋ ๋ ๊ฒ ๊ฐ์๋ค.
์ฐ๋ฆฌ๊ฐ ์๋ฒ์ ์ฃผ๊ณ ๋ฐ์์ผ ํ๋ ๋ฐ์ดํฐ๊ฐ ๊ทธ๋ฆฌ ๋ง์ง ์๊ธฐ ๋๋ฌธ์ ๋๋์ฑ ๊ทธ๋ฌ๋ค.
3. Community Detection ์๊ณ ๋ฆฌ์ฆ ๊ฐ์
ํ์ฌ Union-Find ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํด์ ๊ฐ์ ์งํฉ๋ด์ ์๋ ๋
ธ๋๋ค์ ํ์งํ๊ณ ํด๋น ๋
ธ๋๋ค์ ๋์ผํ ์์์ผ๋ก ์น ํ๋๋ก ๊ตฌํ์ ํด๋์๋ค.
๋ฌธ์ ๋ ๋
ธ๋๋ฅผ ์ถ๊ฐํ๊ฑฐ๋ ๋
ธ๋, ์ฃ์ง๋ฅผ ์ญ์ ํ ๋ ์ปค๋ฎค๋ํฐ๊ฐ ๋ฐ๋ ์๋ ์๋ค๋ ์ ์ด๋ค.
์์ ๊ฒฝ์ฐ์์ 2, 4๋ฒ ์ฌ์ด์ ์๋ก์ด ๊ฐ์ ์ ์์ฑํ๊ฒ ๋๋ฉด ๊ธฐ์กด์ ๋ ์ปค๋ฎค๋ํฐ๊ฐ ํ๋๋ก ํฉ์ณ์ง๊ฒ ๋๋ค.
๊ทธ๋ฌ๋ฉด ๋ชจ๋ ๋
ธ๋๋ฅผ ์ด๋ก ๋๋ ์ฃผํฉ์ผ๋ก ์์น ์ ํด์ผ ํ๋๋ฐ 2, 4๋ฒ์ Union ํ๊ฒ ๋๋ฉด ์กฐ์์ ๋ชจ๋ ๊ฐ์์ง๋ฏ๋ก ๊ฐ์ ์ปค๋ฎค๋ํฐ์ ๋ฃ์ ์๋ ์์ง๋ง, ๊ฐ ๋
ธ๋๊ฐ ๊ฐ์ง๊ณ ์๋ ์์ ์ ๋ณด๋ ํต์ผ๋์ง ์๋๋ค.
๊ฒฐ๊ตญ ๋ชจ๋ ๋
ธ๋๋ฅผ ๋๋ฉด์ ๋ค์ ์์์ ์น ํด์ฃผ์ด์ผ ํ๋ ๋ฌธ์ ๊ฐ ๋ฐ์ํ๋ค.
๋ฌผ๋ก ๊ทธ๋ํ์ ํ์ํ ๋ฐ์ดํฐ์ ์๊ฐ ๊ทธ๋ ๊ฒ ๋ง์ง ์์ ๊ฒ์ด๊ธฐ ๋๋ฌธ์ ์ถฉ๋ถํ ๋์์ ํ ์ ์์ง๋ง, ๋งค๋ฒ ๋ถํ์ํ ์ฐ์ฐ์ ๋ง์ด ํ๋ ๊ฒ ๊ฐ์์ ๊ฐ์ ์ด ํ์ํด ๋ณด์๋ค.
๋ง์นจ ๊ต์๋์ด ์๊ณ ๋ฆฌ์ฆ์ ์ ๋ฌธ์ ์ผ๋ก ํ์๊ธฐ ๋๋ฌธ์ ์ฌ์ญค๋ณผ ์ ์์๋ค.
๊ต์๋์ ๊ฐ ์ปค๋ฎค๋ํฐ์ ๋ค์ด์๋ ๋ ธ๋๋ค์ linked-list ํํ๋ก ๋งค๋ฌ์๋ ๋ค์์, Union์ด ๋ฐ์ํ๋ฉด ํ์ชฝ ์ปค๋ฎค๋ํฐ์ ์๋ ๋ ธ๋๋ง ๋๋ฉด์ ์์๊ฐ์ ๋ฐ๊ฟ์ฃผ๊ณ linked-list๋ฅผ ๋ถ์ฌ์ฃผ๊ธฐ๋ง ํ๋ฉด ์ด๋ ๋๊ณ ํ์ จ๋ค.
์ถ๊ฐ์ ์ธ ์ ๋ณด๋ฅผ ์ ์ฅํด์ผ ํ๋ค๋ ์ค๋ฒํค๋๋ ์์์ง๋ง, ๊ทธ๋ ๊ฒ ํฌ์ง๋ ์๊ณ ๋งค๋ฒ ๋ชจ๋ ๋
ธ๋์ ๋ํด Union-Find๋ฅผ ์งํํ๋ ๊ฒ๋ณด๋ค๋ ํจ์ฌ ํจ์จ์ ์ด๋ผ๊ณ ์๊ฐํ๋ค.
ํ๋ก ํธ์์ ์ด๋ฐ ์๊ณ ๋ฆฌ์ฆ์ ๊ตฌํํด๋ณธ ์ ์ด ์์ด์ ๊ตฌํํ ์ ์์์ง๊ฐ ์๋ฌธ์ด์์ง๋ง ๋์ ํด๋ณด๊ธฐ๋ก ํ๋ค.
Union-Find๋ ์ด๋ฆ ๊ทธ๋๋ก ํฉ์น๋ ์๊ณ ๋ฆฌ์ฆ์ด์ง ํด์ฒด์ ๋ํ ์๊ณ ๋ฆฌ์ฆ์ด ์๋๊ธฐ ๋๋ฌธ์ ๊ฐ์ ์ด ์ญ์ ๋์ด ์ปค๋ฎค๋ํฐ๊ฐ ๋ถ๋ฆฌ๋๋ ๊ฒฝ์ฐ์๋ ์ด์ฉ ์ ์์ ๊ฒ ๊ฐ๋ค๊ณ ํ์ จ๋ค.
์ถํ ์งํ ๋ฐฉํฅ
ํผ๋๋ฐฑ๊ณผ ๋ ผ์์ฌํญ์ ๋ฐํ์ผ๋ก ๋ค์์ ์งํํด์ผ ํ ์์ ๋ค์ ์ ๋ฆฌํด๋ณด์๋ค.
1. Community Detection์ ์ฌ์ฉ๋๋ Louvain ์๊ณ ๋ฆฌ์ฆ ์ฐพ์๋ณด๊ธฐ
๋ง์ฝ Louvain ์๊ณ ๋ฆฌ์ฆ์ด Union-Find ๋ณด๋ค ๋์ ์ธ Community Detection์ ์ ๋ฆฌํ๋ค๋ฉด ํด๋น ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํ๋ ๊ฒ์ด ๋ ์ข์ ์๋ ์๋ค.
2. ์๋ฒ ๊ตฌ์ถํ๊ธฐ
์ฐ๊ตฌ์ค ์๋ฒ ์ปดํจํฐ์ ์๋ฒ๋ฅผ ๊ตฌ์ถํ๊ณ , ์๊ฒฉ์ผ๋ก ์ ์ํด์ ์์
์ ์ด์ด๋๊ฐ๋ฉด ๋ ๊ฒ ๊ฐ๋ค.
3. ๊ธฐ์กด์ ์๋ ์ต์ ๋ค ์กฐ๊ธ์ฉ ์ ์ฉํด๋๊ฐ๊ธฐ
'HYU > ์กธ์ ํ๋ก์ ํธ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
7. ์น ์๋ฒ ๊ตฌ์ (0) | 2024.03.20 |
---|---|
6. ๋ ธ๋ ์ญ์ ๋ฐ ๊ฐ์ ์ถ๊ฐ ๊ธฐ๋ฅ ๊ฐ์ (0) | 2024.03.17 |
4. ํ์ด์ง ๋ ์ด์์ ๋์์ธ ๋ฐ ๋ณ๊ฒฝ (0) | 2024.02.26 |
3. Community Detection (2) | 2024.02.09 |
2. Layout ํ์ ๋ฐ ์ฑ๋ฅ ์ธก์ (0) | 2024.01.31 |