應用特徵分析探索有向網絡之拓撲結構

Applying Eigen Analysis to Explore Topological Structures of Directed Networks

盧能彬(Neng-Pin Lu)

《電子商務學報》 16卷4期 (2014/12) Pp. 461-490

https://doi.org/10.6188/JEB.2014.16(4).04

摘要

在圖形理論中，相鄰矩陣為表示網絡的基本資料結構；而在線性代數中，一個矩陣經由特徵分析則可找出其特徵值與對應之特徵向量。因此，透過相鄰矩陣的特徵分析將可協助網絡拓撲結構的解析：若綜觀整體特徵向量，可探索整體網絡的聚合次團體；若微觀特徵向量的個別元素值，則可分別評估各個節點的中心性。由於無向網絡的相鄰矩陣為對稱、可以對角化，目前已有許多特徵分析的研究結果。然而，由於有向網絡的相鄰矩陣不一定對稱、不一定可以對角化，所以其特徵分析的研究結果仍然相當有限。因此，本研究嘗試以相鄰矩陣的特徵分析，探索有向網絡的拓撲結構，包含強連通圖形、單一領結結構、以及遞迴領結結構等，進而瞭解有向網絡的相關特徵性質，據以提出一個有向網絡特徵分析演算法，並實務應用在部落格好友網絡，探索其中的拓撲結構。

關鍵字

社會網絡分析 ； 特徵分析 ； 領結結構

並列摘要

In graph theory, the adjacency matrix is the basic data structure to represent a network; in linear algebra, the eigenvalues and corresponding eigenvectors of a matrix can be found out via an eigen analysis. Therefore, the eigen analysis of adjacency matrix is an approach to investigating topological structures of networks. After an eigen analysis of adjacency matrix, by inspecting the eigenvectors from the macro view, we can explore cohesive subgroups of the whole network; and by inspecting the elements of eigenvectors from the micro view, we can evaluate centrality of the individual nodes. In the literature, there have been many eigen analytical results of undirected networks thanks to symmetric and diagonalizable adjacency matrices. However, adjacency matrices of direct networks may be asymmetric and not diagonalizable so that the eigen analytical results of direct networks are rare to date. Therefore, in this paper, we try to apply the eigen analysis of adjacency matrix to explore topological structures of directed networks, including the strongly connected graph, simple bowtie structure, and recursive bowtie structure, to further the understandings of eigen properties of directed networks. As a result, we propose an eigen analysis algorithm for directed networks in theory and apply the algorithm to explore topological structures of blogroll networks in practice.

並列關鍵字

Social Network Analysis ； Eigen Analysis ； Bowtie Structure

參考文獻

盧能彬(2013).部落格空間之核心社群探索.電子商務學報.15(2),235-264.

Adar, E.,Adamic, L. A.(2005).Tracking Information Epidemics in Blogspace.Proceedings of the 2005 IEEE/WIC/ACM International Conference on Web Intelligence.(Proceedings of the 2005 IEEE/WIC/ACM International Conference on Web Intelligence).:

Aho, A. V.,Garey, M. R.,Ullman, J. D.(1972).The transitive reduction of a directed graph.SIAM Journal on Computing.1(2),131-137.

Baird, C. H.,Parasnis, G.(2011).From social media to social CRM: What customers want.IBM Global Business Services Executive Report, GBE03391-USEN-00.(IBM Global Business Services Executive Report, GBE03391-USEN-00).,::IBM.

Bakshy, E.,Karrer, B.,Adamic, L.(2009).Social influence and the diffusion of usercreated content.Proceedings of the 10th ACM Conference on Electronic Commerce.(Proceedings of the 10th ACM Conference on Electronic Commerce).: