군집을 찾는 알고리즘2 - Louvain algorithm

주어진 그래프의 개별 정점에서부터 점점 군집을 병합해가는 상향식 알고리즘  1. first phase - modularity optimization 처음 주어진 상태에서는 개별 node 1개씩이 하나의 군집이라고 생각 특정 node i를 그것의 이웃(neighbor)인 j에 병합시키면서 modularity의 변화량을 계산함 원래 상태의 modularity와 이웃인 j에 병합시킨 뒤 modularity의 차이를 계산한다. 병합시키면 군집이 생기니까 modularity는 최소한 감소하지는 않음 이 때 최대로 modularity가 증가하는 이웃 j가 있을 것인데 그곳에 i를 포함시킨다. 증가하는 경우가 없다면 어떠한 곳에도 포함시키지 않는다. 다시 다른 node v를 선택하여 위 과정을 반복, 모든 node에..

• format_list_bulleted Graph
• · 2024. 9. 4.
• textsms

군집을 찾는 알고리즘1 - Girvan-Newman algorithm

1. idea 군집을 찾는 대표적인 하향식 알고리즘으로 전체 그래프에서 시작하여 군집들이 서로 분리되도록 link를 순차적으로 제거함 서로 다른 군집을 연결하는 다리 역할을 하는 link를 먼저 제거해나가야 군집들이 분리 될 것이다.   2. betweenness centrality 그래프의 임의의 두 node의 최단 경로 위에 특정 link가 몇번이나 놓이는지 계산    link A-B는 양 옆 4개의 node중 하나를 선택하여 만든 최단 경로에 모두 존재해야하므로 4*4=16가지가 있다. 따라서 그림을 보면 직관적으로 betweenness centrality가 높은 link는 두 군집을 연결하는 다리 역할을 할 가능성이 높다.   3. algorithm 주어진 그래프에서 모든 link의 매개 중심성을..

• format_list_bulleted Graph
• · 2024. 9. 1.
• textsms

그래프의 군집구조(community)

1. 군집(community) 군집은 다음 두가지 조건을 모두 만족하는 하나의 node 집합이다. 1) 집합에 속하는 node 사이에 충분히 많은 link가 있다.2) 그러한 집합에 속하는 node와 속하지 않는 node 사이에는 충분히 적은 link가 있다. 딱 봐도 수학적인 정의는 아니지만 눈으로 보기에 군집을 구별하는 것은 쉽다   2. example  SNS의 군집들은 사회적으로 의미있는 사회적 무리(Social circle)를 형성   실제 SNS에서는 돈을 받고 팔로워를 늘려주는 경우도 많다.   하나의 조직 내 분란으로 인해 군집이 형성   내분으로 동아리가 둘로 나뉘었다는데??   회사 내 이메일 네트워크나 보고체계를 분석하여 그래프로 나타내면 회사 커뮤니케이션이 얼마나 효율적인지 알아볼 ..

• format_list_bulleted Graph
• · 2023. 7. 24.
• textsms

그래프를 여러 집단으로 나누는 방법

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A,B,C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. ..

• format_list_bulleted 알고리즘 일반
• · 2022. 4. 9.
• textsms