Community Detection with Colored Edges여러 종류의 연결을 포함한 그래프에서의 커뮤니티 검출

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 322
  • Download : 0
In this paper, we prove a sharp limit on the community detection problem with colored edges. We assume two equal-sized communities and there are $m$ different types of edges. If two vertices are in the same community, the distribution of edges follows $p_i=\alpha_i\log{n}/n$ for $1\leq i \leq m$, otherwise the distribution of edges is $q_i=\beta_i\log{n}/n$ for $1\leq i \leq m$, where $\alpha_i$ and $\beta_i$ are positive constants and $n$ is the total number of vertices. Under these assumptions, a fundamental limit on community detection is characterized using the Hellinger distance between the two distributions. If $\sum_{i=1}^{m} {(\sqrt{\alpha_{i}}-\sqrt{\beta_{i}})}^{2}>2$, then the community detection via maximum likelihood (ML) estimator is possible with high probability. If $\sum_{i=1}^{m} {(\sqrt{\alpha_{i}}-\sqrt{\beta_{i}})}^{2}<2$, the probability that the ML estimator fails to detect the communities does not go to zero.
Advisors
Chung, Sae-Youngresearcher정세영researcher
Description
한국과학기술원 :전기및전자공학부,
Publisher
한국과학기술원
Issue Date
2017
Identifier
325007
Language
eng
Description

학위논문(석사) - 한국과학기술원 : 전기및전자공학부, 2017.2,[i, 19 :]

Keywords

Community detection problem; Hellinger distance; 커뮤니티 검출 문제; 헬링거 거리

URI
http://hdl.handle.net/10203/243272
Link
http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=675397&flag=dissertation
Appears in Collection
EE-Theses_Master(석사논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0