TY - JOUR
T1 - Using eigenvectors of perturbed and collapsed adjacency matrices to explore bowtie structures in directed networks
AU - Lu, Neng Pin
N1 - Publisher Copyright:
© 2016 The Chinese Institute of Engineers.
PY - 2016/11/16
Y1 - 2016/11/16
N2 - The bowtie structure can illustrate not only the accessibility of the World Wide Web, but also the reachability of other directed networks. In this paper, we use the principal eigenvectors of the adjacency matrix with the unique largest eigenvalue to identify the strongly connected component of a directed network and fit the network into the bowtie structure. To ensure that the largest eigenvalue is unique, we add a little perturbation to the matrix before the eigen analysis. After the revelation of the bowtie structure centered on the strongly connected component with the largest unique eigenvalue, a directed network may have other bowtie structures centered on strongly connected components with smaller eigenvalues. To reveal other bowtie structures, we collapse the perturbed matrix by aggregating nodes of the strongly connected component with the largest eigenvalue into a supernode. Hence, the principal eigenvectors of the perturbed and collapsed matrix can be used to reveal the bowtie structure centered on the strongly connected component with the second largest eigenvalue. Furthermore, repeating the process of collapsing a strongly connected component and finding principal eigenvectors of the perturbed and collapsed matrix, we can reveal all the bowtie structures of a directed network.
AB - The bowtie structure can illustrate not only the accessibility of the World Wide Web, but also the reachability of other directed networks. In this paper, we use the principal eigenvectors of the adjacency matrix with the unique largest eigenvalue to identify the strongly connected component of a directed network and fit the network into the bowtie structure. To ensure that the largest eigenvalue is unique, we add a little perturbation to the matrix before the eigen analysis. After the revelation of the bowtie structure centered on the strongly connected component with the largest unique eigenvalue, a directed network may have other bowtie structures centered on strongly connected components with smaller eigenvalues. To reveal other bowtie structures, we collapse the perturbed matrix by aggregating nodes of the strongly connected component with the largest eigenvalue into a supernode. Hence, the principal eigenvectors of the perturbed and collapsed matrix can be used to reveal the bowtie structure centered on the strongly connected component with the second largest eigenvalue. Furthermore, repeating the process of collapsing a strongly connected component and finding principal eigenvectors of the perturbed and collapsed matrix, we can reveal all the bowtie structures of a directed network.
KW - Directed network
KW - adjacency matrix
KW - bowtie structure
KW - eigenvector
UR - http://www.scopus.com/inward/record.url?scp=84987664725&partnerID=8YFLogxK
U2 - 10.1080/02533839.2016.1225517
DO - 10.1080/02533839.2016.1225517
M3 - 文章
AN - SCOPUS:84987664725
SN - 0253-3839
VL - 39
SP - 936
EP - 945
JO - Journal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an
JF - Journal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an
IS - 8
ER -