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

Applying Eigen Analysis to Explore Topological Structures of Directed Networks

10.6188/JEB.2014.16(4).04

盧能彬(Neng-Pin Lu)

社會網絡分析 ； 特徵分析 ； 領結結構 ； Social Network Analysis ； Eigen Analysis ； Bowtie Structure

電子商務學報

16卷4期（2014 / 12 / 01）

461 - 490

繁體中文

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

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.

1. 盧能彬(2013).部落格空間之核心社群探索.電子商務學報,15(2),235-264.
   連結：
2. Borgatti, S. P., Everett, M. G., & Freeman, L. C. (2002). Ucinet for Windows: Software for Social Network Analysis. Massachusetts: Analytic Technologies..
3. Adar, E.,Adamic, L. A.(2005).Tracking Information Epidemics in Blogspace.Proceedings of the 2005 IEEE/WIC/ACM International Conference on Web Intelligence,Compiegne, France:
4. 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.
5. Baird, C. H.,Parasnis, G.(2011).IBM Global Business Services Executive Report, GBE03391-USEN-00IBM Global Business Services Executive Report, GBE03391-USEN-00,New York:IBM.
6. Bakshy, E.,Hofman, J.,Mason, W.,Watts, D.(2011).Everyone's an influencer: Quantifying influence on twitter.Proceedings of the fourth ACM International Conference on Web Search and Data Mining,Hong Kong, China:
7. Bakshy, E.,Karrer, B.,Adamic, L.(2009).Social influence and the diffusion of usercreated content.Proceedings of the 10th ACM Conference on Electronic Commerce,Stanford, California, USA:
8. Ball, B.,Newman, M. E. J.(2013).Friendship networks and social status.Network Science,1(1),16-30.
9. Bapat, R. B.,Raghavan, T. E. S.(1997).Nonnegative Matrices and Applications.New York:Cambridge University Press.
10. Bonacich, P.(1972).Factoring and weighting approaches to status scores and clique identification.The Journal of Mathematical Sociology,2(1),113-120.
11. Bonacich, P.(2007).Some unique properties of eigenvector centrality.Social Networks,29(4),555-564.
12. Bonacich, P.(1987).Power and centrality: A family of measures.American Journal of Sociology,92(5),1170-1182.
13. Bonacich, P.,Lloyd, P.(2001).Eigenvector-like measures of centrality for asymmetric relations.Social Networks,23(3),191-201.
14. Borgatti, S. P.,Foster, P. C.(2003).The network paradigm in organizational research: A review and typology.Journal of Management,29(6),991-1013.
15. Borgatti, S. P.,Halgin, D. S.(2011).On network theory.Organization Science,22(5),1168-1181.
16. Breiger, R.,Boorman, S.,Arabie, P.(1975).An algorithm for clustering relational data with applications to social network analysis and comparison with multidimensional scaling.Journal of Mathematical Psychology,12(3),328-383.
17. Brin, S.,Page, L.(1998).The anatomy of a large-scale hypertextual web search engine.Computer Networks and ISDN Systems,30(1),107-117.
18. Broder, A.,Kumar, R.,Maghoul, F.,Raghavan, P.,Rajagopalan, S.,Stata, R.,Tomkins, A.,Wiener, J.(2000).Graph structure in the web.Computer Networks,33(1-6),309-320.
19. Chung, F.(1997).Spectral Graph Theory.Rhode Island:AMS Publications.
20. de Nooy, W.,Mrvar, A.,Batagelj, V.(2005).Exploratory Social Network Analysis with Pajek.New York:Cambridge University Press.
21. Dill, S.,Kumar, R.,McCurley, K. S.,Rajagopalan, S.,Sivakumar, D.,Tomkinst, A.(2002).Self-similarity in the web.ACM Transactions on Internet Technology,2(3),205-223.
22. Domingos, P.(2005).Mining social networks for viral marketing.IEEE Intelligent Systems,20(1),80-82.
23. Domingos, P.,Richardson, M.(2001).Mining the network value of customers.Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,San Francisco, California, USA:
24. Donetti, L.,Munoz, M.A.(2004).Detecting network communities: A new systematic and efficient algorithm.Journal of Statistical Mechanics: Theory and Experiment,10012.
25. Doreian, P.,Batagelj, V.,Ferligoj, A.(2005).Generalized Blockmodeling.New York:Cambridge University Press.
26. Doreian, P.,Batagelj, V.,Ferligoj, A.(2000).Symmetric-acyclic decompositions of networks.Journal of Classification,17(1),3-28.
27. Fielding, N.(ed.),Lee, R. M.(ed.),Blank, G.(ed.)(2008).The SAGE Handbook of Online Research Methods.London:SAGE Publications.
28. Fortunato, S.,Flammini, A.(2007).Random walks on directed networks: The case of PageRank.International Journal of Bifurcation and Chaos,17(7),2343-2353.
29. Freeman, L. C.(2008).Going the wrong way on a one-way street: Centrality in physics and biology.Journal of Social Structure,9(2)
30. Freeman, L. C.(1979).Centrality in social networks: Conceptual clarification.Social Networks,1(3),215-239.
31. Friedkin, N. E.(1991).Theoretical foundations for centrality measures.American Journal of Sociology,96(6),1478-1504.
32. Goel, S.,Watts, D. J.,Goldstein, D. G.(2012).The structure of online diffusion networks.Proceedings of the 13th ACM Conference on Electronic Commerce,Valencia, Spain:
33. Gould, R. V.(2002).The origins of status hierarchies: A formal theory and empirical test.American Journal of Sociology,107(5),1143-1178.
34. Hanneman, R.,Riddle, M.(2005).Introduction to Social Network Methods.California:University of California, Riverside.
35. Holme, P.,Huss, M.(2005).Role-similarity based functional prediction in networked systems: Application to the yeast proteome.Journal of the Royal Society Interface,2(4),327-333.
36. Horn, R. A.,Johnson, C. R.(1985).Matrix Analysis.New York:Cambridge University Press.
37. Hubbell, C.(1965).An input-output approach to clique identification.Sociometry,28(4),377-399.
38. Kadushin, C.(2012).Understanding Social Networks: Theories, Concepts, and Findings.New York:Oxford University Press.
39. Kannan, R.,Vempala, S.(2008).Spectral algorithms.Foundations and Trends in Theoretical Computer Science,4(3-4),132-288.
40. Katz, L.(1953).A new status index derived from sociometric analysis.Psychometrika,18(1),39-43.
41. Leskovec, J.,Adamic, L. A.,Huberman, B. A.(2007).The dynamics of viral marketing.ACM Transactions on the Web,1(1),1-39.
42. Metaxas, P. T.(2012).Why is the shape of the web a bowtie?.Proceedings of the 21st International Conference on World Wide Web,Lyon, France:
43. Moody, J.(2001).Peer influence groups: Identifying dense clusters in large networks.Social Networks,23(4),261-283.
44. Naumann, U.(ed.),Schenk, O.(ed.)(2012).Combinatorial Scientific Computing.Florida:CRC Press.
45. Newman, M. E. J.(2006).Finding community structure in networks using the eigenvectors of matrices.Physical Review E,74(3),036104.
46. Porter, M. A.,Onnela, J. -P.,Mucha, P. J.(2009).Communities in networks.Notices of the AMS,56(9),1082-1166.
47. Ragnaven, U. N.,Albert, R.,Kumara, S.(2007).Near linear time algorithm to detect community structures in large-scale networks.Physical Review E,76(3),036106.
48. Rajaraman, A.,Leskovec, J.,Ullman, J. D.(2012).Mining of Massive Datasets.New York:Cambridge University Press.
49. Richards, W.,Seary, A.(2003).Spectral methods for analyzing and visualizing networks: An introduction.Dynamic Social Network Modeling and Analysis: Workshop Summary and Papers,Washington, DC:
50. Richards, W.,Seary, A.(2000).Eigen analysis of networks.Journal of Social Structure,1(2),1-17.
51. Sahni, S.(2001).Data Structures, Algorithms, and Applications in Java.New York:McGraw-Hill.
52. Scott, J.(ed.),Carrington, P. J.(ed.)(2011).The SAGE Handbook of Social Network Analysis.London:SAGE Publications.
53. Sun, E.,Rosenn, I.,Marlow, C.,Lento, T.(2009).Gesundheit! Modeling contagion through facebook news feed.Third International AAAI Conference on Weblogs and Social Media,San Jose, California, USA:
54. Vitali, S.,Glattfelder, J. B.,Battiston, S.(2011).The network of global corporate control.PLoS ONE,6(10),e25995.
55. Wasserman, S.,Faust, K.(1994).Social Network Analysis: Methods and Applications.New York:Cambridge University Press.
56. Watts, D. J.,Peretti, J.(2007).Viral marketing for the real world.Harvard Business Review,85(5),22-23.
57. White, H. C.,Boorman, S. A.,Breiger, R. L.(1976).Social structure from multiple networks: I. Blockmodels of roles and positions.American Journal of Sociology,81(4),730-780.
58. Wu, F.,Huberman, B. A.(2004).Finding communities in linear time: A physics approach.The European Physical Journal B,38(2),331-338.
59. Zhang, J.,Ackerman, M. S.,Adamic, L.(2007).Expertise networks in online communities: Structure and algorithms.Proceeding of the 16th International Conference on World Wide Web,Banff, Alberta, Canada: