Using eigenvectors of perturbed and collapsed adjacency matrices to explore bowtie structures in directed networks

Neng Pin Lu*

*Corresponding author for this work

Research output: Contribution to journalJournal Article peer-review

3 Scopus citations

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 languageEnglish
Pages (from-to)936-945
Number of pages10
JournalJournal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an
Volume39
Issue number8
DOIs
StatePublished - 16 11 2016
Externally publishedYes

Bibliographical note

Publisher Copyright:
© 2016 The Chinese Institute of Engineers.

Keywords

  • Directed network
  • adjacency matrix
  • bowtie structure
  • eigenvector

Fingerprint

Dive into the research topics of 'Using eigenvectors of perturbed and collapsed adjacency matrices to explore bowtie structures in directed networks'. Together they form a unique fingerprint.

Cite this