modularity4 [네트워크이론] 여러가지 Modularity 들 Newman과 Girvan에 의해 처음 고안된 modularity는 다음과 같다. (자세한 내용은 이전 글 참조) $Q = \frac{1}{2M} \sum\limits_{i, j}^{N} (a_{ij} - \left\langle t_{ij} \right\rangle) \delta(c_{i}, c_{j}) $ $ \left\langle t_{ij} \right\rangle = \frac{k_{i}k_{j}}{2M} $ $ M $ : 총 link 수 $ N $ : 총 node 수 $ a_{ij} $ : node i와 j 사이의 link가 있을 때 1 (없을 때 0) $ \left\langle t_{ij} \right\rangle $ : node i와 j 사이의 link의 기댓값 $ \delta(c_{i}, .. 2021. 9. 24. [네트워크이론] Louvain algorithm for community detection network로부터 community를 추출하는 방법으로 Girvan-Newman algorithm와 Link community를 소개한 적이 있었다. 오늘은 그 3탄으로 Louvain algorithm을 소개하려고 한다. Louvain algorithm이 처음 소개된 논문은 Fast unfolding of communities in large networks, Vincent D et al., Journal of Statistical Mechanics: Theory and Experiment(2008) 이다. 이 알고리즘에 Louvain이라는 이름이 붙은 이유는 벨기에의 Louvain이라는 대학 출신이어서.. 애교심이 대단하다ㅎㅎ 이번 글은 논문의 전개 방식에 맞추어 Louvain algorithm의 배.. 2018. 8. 10. [네트워크이론] Network Modularity 실제 사용 예 Girvan-Newman algorithm [이전 글] 2018/02/18 - [연구/연구] - [네트워크이론] Network Modularity (네트워크의 모듈성) 이전 글에 이어서 이번에는 실제 예제로 계산해 보는 모듈성과 모듈성을 이용한 Girvan-Newman Community 추출 Algorithm에 대한 글을 써본다. 예제로는 30명이 함께 있는 네트워크에서 1팀(8명), 2팀(10명), 3팀(12명)으로 구성된 내부 커뮤니티를 검출할 수 있을까 이다. 이를 위에 다음과 같이 설정하여 사회 네트워크를 구성하고, 이 때의 Modularity를 구해보는 과정을 Python을 이용하여 진행해보자. 설정 1. 각각의 사람은 0~29의 숫자로 표현한다. 2. 팀 설정1팀: 0~72팀: 8~173팀: 18~29 3. 커뮤니티 l에서 커뮤니티 l.. 2018. 2. 18. [네트워크이론] Network Modularity (네트워크의 모듈성) 네트워크를 바라보면, 네트워크 속에서도 끼리끼리 뭉쳐있는 커뮤니티가 보이곤 한다. 다음 네트워크를 예로 들어보자. 네트워크지만, 위쪽 아래쪽 왼쪽으로 끼리끼리 모여있는 3개의 작은 커뮤니티가 있는 것처럼 보인다. 그렇다면 이를 어떻게 찾아낼 수 있을 것인가? 위의 그림의 3개의 커뮤니티에 대한 label이 존재한다고 생각해보자. 이 때, 이 네트워크의 커뮤니티 구조는 얼마나 모듈화 되어 있을 것인가? Modularity(모듈성)는 이를 정량적으로 나타내기 위해 등장했다. Modularity는 커뮤니티 내부에 펼쳐져 있는 링크들이 무작위적인 연결들과 비교했을 때 얼마나 더 많은지 정량화 한다. 구체적으로는 원래의 네트워크 G와 각 노드의 링크의 개수를 유지한 체로 대상을 랜덤하게 변화시킨 네트워크 G'와 .. 2018. 2. 18. 이전 1 다음
