Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 936-945 |
Number of pages | 10 |
Journal | Journal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an |
Volume | 39 |
Issue number | 8 |
DOIs | |
State | Published - 16 11 2016 |
Externally published | Yes |
Bibliographical note
Publisher Copyright:© 2016 The Chinese Institute of Engineers.
Keywords
- Directed network
- adjacency matrix
- bowtie structure
- eigenvector