Connected Component Analysis on an Undirected Graph

버전 (4.96 KB) 작성자: Tristan Ursell
Connected component analysis on undirected graphs, with thresholding and connectivity constraints.
다운로드 수: 515
업데이트 날짜: 2012/8/30

라이선스 보기

Tristan Ursell
April 2012
Connected component analysis on an undirected graph, with various thresholding and connectivity constraints.

[groups,orphans] = graph_analysis(W);
[groups,orphans] = graph_analysis(W,'field',value,...);
[groups,~] = graph_analysis(W,'field',value,...);

W is the N x N adjaceny matrix for a symmetric graph. Thus W should be a symmetric matrix, if it is not, this function will give an error. Self connections (i.e. diagonal elements) are not allowed and will be removed automatically. The values of the parameters below are applied as a union set, that is, all original elements must meet all of the conditions specified by the parameters to be included in a group of connected components.

If only W is given, then all components with W > 0 will be analyzed and grouped, with the default constraints.

'min_conn' (0 <= min_conn <= max_conn) specifies the minimum degree of connectivity (not including itself) for any element in W to be included in a group. The default 'min_conn' value is 1.

'max_conn' (min_conn <= max_conn <= N) specifies the maximum degree of connectivity for any element in W to be included in a group. The default 'max_conn' value is N.

'min_like' is the minimum likelihood value for an element in W to be included in any group. The default value is 0. The 'likelihood' is not necessarily a probability, and hence is not bounded between zero and one. However, for any two elements in W, the ratio of likelihoods should be equal to their ratio of probabilities.

'max_link' is the maximum number of linkages to search for in the network. This parameter is useful when you know that the network has some maximum number of connections between the elements in the network (e.g. if the graph has the property that any two two nodes are no more than N connections away, you can seg max_lin = N, to speed up the code). Choosing smaller values of 'max_link' can significantly speed the code. The default value is the size of the current sub-block.

'max_rank' (1 <= max_rank <= N) is the number of highest likelihood values to use in forming connected groups. For instance, if max_rank = 3, and a row of W is:

1 3 6 4 4 5 6 8 0 3 1

then the matrix row will become:

0 0 1 0 0 0 1 1 0 0 0

If a row of W is:

1 3 6 4 4 6 6 6 0 3 1

with max_rank = 1,2,3 or 4, the row becomes:

0 0 1 0 0 1 1 1 0 0 0

with max_rank = 5, the same row becomes:

0 0 1 1 1 1 1 1 0 0 0

The default value of 'max_rank' is N.

'plot' with value 1 will generate plots of the grouping algorithm as it creates block diagonal groups in from top left to bottom right in W.

The output 'groups' is a structure array with fields:

groups(i).num_els = number of elements in group i.
groups(i).block = sub-block identity of group i.
groups(i).elements = elements of W that are in group i.
groups(i).degrees = degrees of connection for each element in group i.
orphans = elements of W that were not in any group, becasue they did not meet the constraints.

The number of distinct groups is length(groups).

Example with a block diagonal random matrix W:


axis equal tight
xlabel('Elements of W')
ylabel('Elements of W')
title('Random Block-Diagonal Adjacency Matrix')

%more inclusive connections, less inclusive probability

%less inclusive connections, more inclusive probability

인용 양식

Tristan Ursell (2024). Connected Component Analysis on an Undirected Graph (, MATLAB Central File Exchange. 검색됨 .

MATLAB 릴리스 호환 정보
개발 환경: R2009b
모든 릴리스와 호환
플랫폼 호환성
Windows macOS Linux
Help CenterMATLAB Answers에서 Undirected Graphs에 대해 자세히 알아보기

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
버전 게시됨 릴리스 정보

improved memory usage, so that 32 bit systems can handle larger arrays.

put 'modone' function inside of m-file as requested by multiple users.

added new features, improved plot handling, reduced memory load and fixed precision error.

fixed some typos in the directions

Improved description.