centrality

노드 중요도 측정

구문

C = centrality(G,type)

C = centrality(___,Name,Value)

설명

C = centrality(G,type)은 그래프의 각 노드에 대해 type로 지정된 노드 중심성을 계산합니다.

C = centrality(___,Name,Value)는 하나 이상의 이름-값 쌍의 인수로 지정된 추가 옵션을 사용합니다. 예를 들어, centrality(G,'closeness','Cost',c)는 각 간선을 순회하는데 드는 비용을 지정합니다.

예제

6개 웹사이트의 페이지 랭크

가상의 웹사이트 6개를 포함하는 그래프를 생성하고 플로팅합니다.

s = [1 1 2 2 3 3 3 4 5];
t = [2 5 3 4 4 5 6 1 1];
names = {'http://www.example.com/alpha', 'http://www.example.com/beta', ...
         'http://www.example.com/gamma', 'http://www.example.com/delta', ...
         'http://www.example.com/epsilon', 'http://www.example.com/zeta'};
G = digraph(s,t,[],names);
plot(G,'NodeLabel',{'alpha','beta','gamma','delta','epsilon','zeta'})

centrality 함수를 사용하여 각 웹사이트의 페이지 랭크를 계산합니다. 그래프의 Nodes 테이블에 이 정보를 그래프 노드의 특성으로 추가합니다.

pg_ranks = centrality(G,'pagerank')

pg_ranks = 6×1

    0.3210
    0.1706
    0.1066
    0.1368
    0.2008
    0.0643

G.Nodes.PageRank = pg_ranks;
G.Nodes

ans=6×2 table
                   Name                   PageRank
    __________________________________    ________

    {'http://www.example.com/alpha'  }    0.32098 
    {'http://www.example.com/beta'   }    0.17057 
    {'http://www.example.com/gamma'  }    0.10657 
    {'http://www.example.com/delta'  }    0.13678 
    {'http://www.example.com/epsilon'}    0.20078 
    {'http://www.example.com/zeta'   }    0.06432 

또한 centrality를 사용하여 hubs와 authorities에 해당하는 노드를 확인하고 Nodes 테이블에 점수를 추가합니다.

hub_ranks = centrality(G,'hubs');
auth_ranks = centrality(G,'authorities');
G.Nodes.Hubs = hub_ranks;
G.Nodes.Authorities = auth_ranks;

G.Nodes

ans=6×4 table
                   Name                   PageRank       Hubs       Authorities
    __________________________________    ________    __________    ___________

    {'http://www.example.com/alpha'  }    0.32098        0.24995    7.3237e-05 
    {'http://www.example.com/beta'   }    0.17057        0.24995      0.099993 
    {'http://www.example.com/gamma'  }    0.10657        0.49991      0.099993 
    {'http://www.example.com/delta'  }    0.13678     9.1536e-05       0.29998 
    {'http://www.example.com/epsilon'}    0.20078     9.1536e-05       0.29998 
    {'http://www.example.com/zeta'   }    0.06432              0       0.19999 

임의 그래프의 연결 중심성(Degree centrality)

임의의 희소 인접 행렬을 사용하여 가중 그래프(Weighted Graph)를 생성하고 플로팅합니다. 간선이 많이 있으므로 EdgeAlpha에 매우 작은 값을 사용하여 간선을 거의 투명하게 만듭니다.

A = sprand(1000,1000,0.15);
A = A + A';
G = graph(A,'omitselfloops');
p = plot(G,'Layout','force','EdgeAlpha',0.005,'NodeColor','r');

각 노드의 연결 중심성을 계산합니다. 간선 가중치를 사용하여 각 간선의 중요도를 지정합니다.

deg_ranks = centrality(G,'degree','Importance',G.Edges.Weight);

discretize를 사용하여 노드 중심성 점수에 따라 간격이 같은 7개의 Bin에 노드를 배치합니다.

edges = linspace(min(deg_ranks),max(deg_ranks),7);
bins = discretize(deg_ranks,edges);

플롯에서 각 노드의 크기를 해당 중심성 점수에 비례하게 만듭니다. 각 노드의 마커 크기는 Bin 숫자(1-7)와 같습니다.

p.MarkerSize = bins;

미네소타 도로의 근접 중심성과 매개 중심성

미네소타의 도로망을 나타내는 graph 객체 G가 포함된 minnesota.mat의 데이터를 불러옵니다. 그래프 노드에는 G.Nodes 테이블의 XCoord 변수와 YCoord 변수에 들어 있는 xy 좌표가 포함되어 있습니다.

load minnesota.mat
xy = [G.Nodes.XCoord G.Nodes.YCoord];

도로의 길이와 대략적으로 일치하는 간선 가중치를 그래프에 추가합니다. 간선 가중치는 각 간선 끝 노드의 xy 좌표 간 유클리드 거리(Euclidean Distance)를 사용하여 계산됩니다.

[s,t] = findedge(G);
G.Edges.Weight = hypot(xy(s,1)-xy(t,1), xy(s,2)-xy(t,2));

노드에 xy 좌표를 사용하여 그래프를 플로팅합니다.

p = plot(G,'XData',xy(:,1),'YData',xy(:,2),'MarkerSize',5);
title('Minnesota Road Network')

각 노드의 근접 중심성을 계산합니다. 노드 색 NodeCData를 중심성 점수에 비례하도록 스케일링합니다.

ucc = centrality(G,'closeness');
p.NodeCData = ucc;
colormap jet
colorbar
title('Closeness Centrality Scores - Unweighted')

또한 간선 가중치를 각 간선을 순회하는 비용으로 사용하여 가중 근접 중심성 점수를 계산합니다. 이제 거리가 이동한 간선의 수가 아니라 이동한 간선 길이의 총합으로 측정되므로 도로 길이를 간선 가중치로 사용하면 점수 품질이 개선됩니다.

wcc = centrality(G,'closeness','Cost',G.Edges.Weight);
p.NodeCData = wcc;
title('Closeness Centrality Scores - Weighted')

그래프의 가중 매개 중심성(Betweenness centrality) 점수를 계산하여 두 노드 간 최단 경로에서 가장 자주 발견되는 도로를 확인합니다. 인수 $$\frac{(n-2)(n-1)}{2}$$을 사용하여 중심성 점수를 정규화하므로 점수는 이동자(Traveler)가 임의의 두 노드 간 최단 경로를 따라 지정된 노드를 통해 이동할 확률을 나타냅니다. 플롯에는 도시로 들어오고 나가는 매우 중요한 도로가 여러 개인 것으로 나타나 있습니다.

wbc = centrality(G,'betweenness','Cost',G.Edges.Weight);
n = numnodes(G);
p.NodeCData = 2*wbc./((n-2)*(n-1));
colormap(flip(autumn,1));
title('Betweenness Centrality Scores - Weighted')

입력 인수

G — 입력 그래프

graph 객체 | digraph 객체

입력 그래프로, graph 객체 또는 digraph 객체로 지정됩니다. 무방향 그래프를 생성하려면 graph를 사용하고 유방향 그래프를 생성하려면 digraph를 사용하십시오.

예: G = graph(1,2)

예: G = digraph([1 2],[2 3])

type — 노드 중심성 유형

'degree' | 'outdegree' | 'indegree' | 'closeness' | 'incloseness' | 'outcloseness' | 'betweenness' | 'pagerank' | 'eigenvector' | 'hubs' | 'authorities'

노드 중심성 유형으로, 표에 나와 있는 옵션 중 하나로 지정됩니다. 다음 표에는 각 유형과 호환 가능한 이름-값 인수가 나열되어 있습니다. 노드 중심성마다 그래프의 노드 중요도에 대해 각기 다른 측정값을 제공합니다.

옵션	그래프 유형	설명	이름-값 인수
'degree'	무방향	'degree', 'outdegree', 'indegree' 중심성 유형은 각 노드에 연결되어 있는 간선 개수를 기반으로 합니다. 'degree' — 각 노드에 연결되어 있는 간선 개수입니다. 자가 루프는 두 개의 간선이 노드에 연결된 것으로 간주됩니다. 'indegree' — 각 노드에 대한 진입 간선 개수입니다. 자가 루프는 하나의 진입 간선으로 간주됩니다. 'outdegree' — 각 노드의 진출 간선 개수입니다. 자가 루프는 하나의 진출 간선으로 간주됩니다. 'Importance' 간선 가중치를 지정하면 알고리즘은 연결된 간선의 개수가 아닌 간선 가중치의 합을 사용합니다.	'Importance'
'indegree' 'outdegree'	유방향
'closeness'	무방향	'closeness', 'incloseness', 'outcloseness' 중심성 유형은 그래프의 한 노드에서 다른 모든 노드까지 거리의 역합을 사용합니다. 도달할 수 없는 노드가 있는 경우 노드 i의 중심성은 다음과 같습니다. $$c\left(i\right)={\left(\frac{A_i}{N-1}\right)}^2\frac{1}{C_i}.$$ Ai는 노드 i에서 도달할 수 있는 노드 개수(i는 세지 않음)이고, N은 G의 노드 개수이고, Ci는 노드 i에서 도달 가능한 모든 노드까지의 거리의 합입니다. 노드 i에서 도달할 수 있는 노드가 없는 경우 c(i)는 0입니다. 'incloseness'의 경우 거리 측정값은 모든 노드에서 노드 i까지의 측정값입니다. 'Cost' 간선 가중치는 간선의 길이를 지정합니다.	'Cost'
'incloseness' 'outcloseness'	유방향
'betweenness'	무방향 또는 유방향	'betweenness' 중심성 유형은 그래프에서 두 노드 간의 최단 경로에 각 그래프 노드가 나타나는 빈도를 측정합니다. 두 그래프 노드 s와 t 사이에는 최단 경로가 여러 개 있을 수 있으므로 노드 u의 중심성은 다음과 같습니다. $$c\left(u\right)={\displaystyle \sum _{s,t\ne u}\frac{n_{st}\left(u\right)}{N_{st}}}.$$ $$n_{st}\left(u\right)$$는 노드 u를 지나가는, s에서 t까지의 최단 경로 개수이고, $$N_{st}$$는 s에서 t까지의 총 최단 경로 개수입니다. 그래프가 무방향이면 s에서 t까지의 경로와 t에서 s까지의 경로가 하나의 경로로만 간주됩니다(식을 2로 나눔). 'Cost' 간선 가중치는 간선의 길이를 지정하며, 노드 s와 t 사이의 최단 경로를 파악하는 데 도움이 됩니다.	'Cost'
'pagerank'	무방향 또는 유방향	'pagerank' 중심성 유형은 네트워크의 무작위 행보(Random Walk) 현상에 대비하기 위한 유형입니다. 그래프의 각 노드에서, 다음 노드는 현재 노드의 후속 노드 집합에서 'FollowProbability' 확률로 선택됩니다(무방향의 경우 인접 노드에서 선택). 이런 식으로 선택되지 않거나 노드에 후속 노드가 없는 경우 다음 노드는 모든 노드에서 선택됩니다. 중심성 점수는 무작위 행보가 발생하는 동안 각 노드에서 소요된 평균 시간입니다. 노드에 자가 루프가 있는 경우에는 알고리즘이 노드를 순회할 가능성이 있습니다. 따라서 자가 루프는 연결 대상 노드의 pagerank 중심성 점수를 늘립니다. 동일한 두 개의 노드 사이에 다중 간선이 있는 다중 그래프에서는 다중 간선을 갖는 노드가 선택될 가능성이 큽니다. 'Importance' 간선 가중치는 알고리즘이 후속 노드를 선택하는 방법에 영향을 미칩니다. 중요도가 높은 노드일수록 선택될 가능성이 큽니다.	'Importance' 'FollowProbability' 'Tolerance' 'MaxIterations'
'eigenvector'	무방향	'eigenvector' 중심성 유형은 그래프 인접 행렬의 최대 고유값에 대응하는 고유벡터를 사용합니다. 점수는 정규화되어, 중심성 점수의 총합은 1이 됩니다. 연결되지 않은 성분이 여러 개 있는 경우 알고리즘은 각 성분에 대해 고유벡터 중심성을 개별적으로 계산한 후 성분의 그래프 노드 비율에 따라 점수를 스케일링합니다. 연결되지 않은 노드의 중심성 점수는 1/numnodes(G)입니다. 계산에 가중치 인접 행렬을 사용하려면 'Importance' 간선 가중치를 지정합니다.	'Importance' 'Tolerance' 'MaxIterations'
'hubs' 'authorities'	유방향	'hubs' 중심성 점수와 'authorities' 중심성 점수는 두 개의 서로 연관된 재귀적 중심성 측정값입니다. 노드의 hubs 점수는 후속 노드 authorities 점수의 총합입니다. 마찬가지로, authorities 점수는 선행 노드 hubs 점수의 총합입니다. hubs 점수의 총합은 1이 되고 authorities 점수의 총합도 1이 됩니다. 이 점수는 인접 행렬의 최대 특이값에 대응하는 좌측(hubs) 특이 벡터와 우측(authorities) 특이 벡터로 해석될 수 있습니다. 연결되지 않은 노드의 중심성 점수는 1/numnodes(G)입니다. 후속 노드 점수/선행 노드 점수의 단순 총합이 아닌 가중 합을 사용하려면 'Importance' 간선 가중치를 지정합니다. 이는 가중치 인접 행렬의 특이 벡터를 사용하는 것과 동일합니다. (약한 연결 측면에서) 연결되지 않은 성분이 여러 개 있는 경우 알고리즘은 각 성분에 대해 hubs 점수와 authorities 점수를 개별적으로 계산합니다. 그런 다음 성분의 그래프 노드 비율에 따라 점수를 다시 스케일링하므로 총합은 여전히 1이 됩니다.	'Importance' 'Tolerance' 'MaxIterations'

참고

centrality 함수에서는 모든 간선 가중치가 1이라고 가정합니다. 이를 변경하려면 'Cost' 이름-값 쌍 또는 'Importance' 이름-값 쌍에 사용할 간선 가중치를 지정하십시오.

예: centrality(G,'degree')

예: centrality(G,'hubs','Tolerance',tol)

이름-값 인수

선택적 인수 쌍을 Name1=Value1,...,NameN=ValueN으로 지정합니다. 여기서 Name은 인수 이름이고 Value는 대응값입니다. 이름-값 인수는 다른 인수 뒤에 와야 하지만, 인수 쌍의 순서는 상관없습니다.

R2021a 이전 릴리스에서는 쉼표를 사용하여 각 이름과 값을 구분하고 Name을 따옴표로 묶으십시오.

예: C = centrality(G,'closeness','Cost',edgeCosts)는 그래프에서 각 간선을 순회하는 비용(가중치)으로 edgeCosts를 사용하여 근접 중심성(Closeness centrality)을 계산합니다.

Cost — 간선을 순회하는 비용

벡터

간선을 순회하는 비용으로, 'Cost'와 함께 간선 가중 벡터가 쉼표로 구분되어 지정됩니다. i번째 간선 가중치는 간선 findedge(G,i)를 순회하는데 관련된 비용을 지정합니다.

• 'closeness', 'outcloseness', 'incloseness' 중심성 유형에 대해 간선 비용은 음수가 아니어야 합니다.

• 'betweenness' 중심성 유형에 대해 간선 비용은 양수여야 합니다.

'Cost' 간선 가중치는 연결이 짧거나 빠르거나 저렴할수록 더 작습니다. 다음은 'Cost' 간선 가중치의 몇 가지 예입니다.

• 경로 길이

• 이동 시간

• 티켓의 비용(Cost)

참고

'Cost'는 'closeness', 'outcloseness', 'incloseness', 'betweenness' 중심성 유형에만 적용됩니다.

예: centrality(G,'closeness','Cost',c)

FollowProbability — 후속 노드 선택 확률

0.85 (디폴트 값) | 0과 1 사이의 스칼라

후속 노드 선택 확률로, 'FollowProbability'와 함께 0과 1 사이의 스칼라가 쉼표로 구분되어 지정됩니다. 후속 확률은 pagerank 알고리즘이 순회 과정에서 선택한 다음 노드가 모든 노드에서 임의로 선택되는 것이 아니라 현재 노드의 후속 노드 중에서 선택되는 확률입니다. 웹사이트의 경우 이 확률은 임의의 다른 웹 페이지로 서핑하는 대신 현재 웹 페이지의 링크를 클릭하는 것에 해당합니다.

참고

'FollowProbability'는 'pagerank' 중심성 유형에만 적용됩니다.

예: centrality(G,'pagerank','FollowProbability',0.5)

Importance — 간선 중요도

벡터

간선 중요도로, 'Importance'와 함께 음이 아닌 간선 가중치 벡터가 쉼표로 구분되어 지정됩니다. i번째 간선 가중치는 간선 findedge(G,i)의 중요도를 지정합니다. 간선 가중치 0은 그래프에서 그에 상응하는 간선을 제거하는 것과 동일합니다.

두 노드 사이에 다중 간선이 있는 다중 그래프에서는 centrality가 이 다중 간선을 모두 더한 다음 이것을 결합된 가중치를 갖는 하나의 간선으로 처리합니다.

'Importance' 간선 가중치는 연결이 강력할수록 더 큽니다. 다음은 'Importance' 간선 가중치의 몇 가지 예입니다.

• 일별 방문자(Traveller) 수

• 링크 클릭 수

• 함께 게시된 문서 수

참고

'Importance'는 'degree', 'outdegree', 'indegree', 'pagerank', 'eigenvector', 'hubs', 'authorities' 중심성 유형에만 적용됩니다.

예: centrality(G,'degree','Importance',x)

MaxIterations — 최대 반복 횟수

100 (디폴트 값) | 스칼라

최대 반복 횟수로, 'MaxIterations'와 함께 스칼라가 쉼표로 구분되어 지정됩니다. centrality 알고리즘은 허용오차가 충족되거나 최대 반복 횟수에 도달할 때까지 실행되는데 이 중 먼저 만족하는 조건이 나오면 중단됩니다.

참고

'MaxIterations'는 'pagerank', 'eigenvector', 'hubs', 'authorities' 중심성 유형에만 적용됩니다.

예: centrality(G,'pagerank','MaxIterations',250)

Tolerance — 반복 솔버의 중지 조건

1e-4 (디폴트 값) | 스칼라

반복 솔버의 중지 조건으로, 'Tolerance'와 함께 스칼라가 쉼표로 구분되어 지정됩니다. centrality 알고리즘은 허용오차가 충족되거나 최대 반복 횟수에 도달할 때까지 실행되는데 이 중 먼저 만족하는 조건이 나오면 중단됩니다.

참고

'Tolerance'는 'pagerank', 'eigenvector', 'hubs', 'authorities' 중심성 유형에만 적용됩니다.

예: centrality(G,'pagerank','Tolerance',1e-5)

출력 인수

C — 노드 중심성 점수

열 벡터

노드 중심성 점수로, 열 벡터로 반환됩니다. C(i)는 노드 i의 중심성 점수입니다. 노드 중심성 점수의 해석은 선택한 중심성 계산 유형에 따라 달라집니다. 노드가 중심에 가까울수록 중심성 점수가 더 큽니다.

확장 기능

스레드 기반 환경
MATLAB®의 backgroundPool을 사용해 백그라운드에서 코드를 실행하거나 Parallel Computing Toolbox™의 ThreadPool을 사용해 코드 실행 속도를 높일 수 있습니다.

버전 내역

R2016a에 개발됨

참고 항목

digraph | graph