Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Một chỉ số trung tâm nhẹ và cục bộ thay thế cho độ trung gian trong phân tích mạng phức tạp
Tóm tắt
Độ trung gian (BWC) của một đỉnh là thước đo tỷ lệ của các đường đi ngắn nhất giữa bất kỳ hai đỉnh nào đi qua đỉnh đó và là một trong những chỉ số trung tâm dựa trên đường đi ngắn nhất được sử dụng rộng rãi trong phân tích mạng phức tạp. Tuy nhiên, để tính toán BWC của chỉ một nút thì mất O(\vert V\vert ^{2}+\vert V\vert \vert E\vert ) thời gian (trong đó V và E lần lượt là tập hợp các nút và cạnh của đồ thị mạng). Giả thuyết của chúng tôi là các nút có bậc cao nhưng hệ số cụm cục bộ thấp có khả năng cao hơn để nằm trên các đường đi ngắn nhất của một vài cặp nút và do đó có thể có giá trị BWC lớn hơn. Do đó, chúng tôi định nghĩa độ trung tâm dựa trên hệ số cụm cục bộ (LCCDC) cho một nút là tích của độ trung tâm của nút và một trừ đi hệ số cụm cục bộ của nút. LCCDC của một nút có thể được tính toán chỉ dựa trên thông tin của khu vực lân cận hai bước của nút đó và sẽ mất ít thời gian hơn rất nhiều. Chúng tôi thực hiện một phân tích tương quan toàn diện và quan sát thấy LCCDC tạo ra các giá trị hệ số tương quan lớn nhất với BWC (so với các chỉ số trung tâm khác dưới ba biện pháp tương quan khác nhau) và duy trì mức độ tương quan dương rất mạnh với BWC trong ít nhất 14 trong số 18 mạng lưới thực tế được phân tích. Do đó, chúng tôi khẳng định rằng LCCDC là một chỉ số thích hợp để xếp hạng các nút hoặc so sánh bất kỳ hai nút nào của một đồ thị mạng thực tế thay cho BWC.
Từ khóa
#độ trung gian #độ trung tâm #mạng phức tạp #hệ số cụm cục bộ #phân tích tương quanTài liệu tham khảo
Newman, M.: Networks: an introduction, 1st edn. Oxford University Press, Oxfrod (2010)
Bonacich, P.: Power and centrality: a family of measures. Am. J. Sociol. 92(5), 1170–1182 (1987)
Freeman, L.: A set of measures of centrality based on betweenness. Sociometry 40(1), 35–41 (1977)
Freeman, L.: Centrality in social networks conceptual clarification. Soc. Netw. 1(3), 215–239 (1979)
Triola, M.F.: Elementary statistics, 12th edn. Pearson, NY (2012)
Lay, D.C.: Linear algebra and its applications, 4th edn. Pearson, NY (2011)
Brandes, U.: A faster algorithm for betweenness centrality. J. Math. Sociol. 25(2), 163–177 (2001)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to algorithms, 3rd edn. MIT Press, Cambridge (2009)
Evans, J.D.: Straightforward Statistics for the Behavioral Sciences, 1st edn, Brooks Cole Publishing Company (1995)
Meghanathan, N.: Spectral radius as a measure of variation in node degree for complex network graphs,. In: Proceedings of the 7th international conference on u- and e- service, science and technology, pp. 30–33, Haikou, China (2014)
Maia de Abreu, N.M.: Old and new results on algebraic connectivity of graphs. Linear Algebra Appl. 423(1), 53–73 (2007)
Newman, M.E.J.: Assortative mixing in networks. Phys. Rev. Lett. 89(2), 208–701 (2002)
Newman, M.E.J.: Modularity and community structure in networks. J. Natl. Acad. Sci. USA 103(23), 8557–8582 (2006)
Cherven, K.: Mastering Gephi network visualization. Packt Publishing, UK (2015)
Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA 99(12), 7821–7826 (2002)
Cross, R.L., Parker, A., Cross, R.: The hidden power of social networks: understanding how work really gets done in organizations. 1st edn. Harvard Business Review Press, NY (2004)
Moreno, J.L.: The sociometry Reader, pp. 534–547, The Free Press, Glencoe (1960)
Freeman, L.C., Webster, C.M., Kirke, D.M.: Exploring social structure using dynamic three-dimensional color images. Soc. Netw. 20(2), 109–118 (1998)
Loomis, C.P., Morales, J.O., Clifford, R.A., Leonard, O.E.: Turrialba social systems and the introduction of change, pp. 45–78, The Free Press, Glencoe (1953)
Nepusz, T., Petroczi, A., Negyessy, L., Bazso, F.: Fuzzy communities and the concept of bridgeness in complex networks. Phys. Rev. E 77(1), 016107 (2008)
Krebs, V.: Proxy networks: analyzing one network to reveal another. Bulletin de Méthodologie Sociologique 79, 40–61 (2003)
Geiser, P., Danon, L.: Community structure in Jazz. Adv. Complex Syst. 6(4), 563–573 (2003)
Pearson, M., Michell, L.: Smoke rings: social network analysis of friendship groups, smoking and drug-taking. Drugs Educ. Prev. Policy 7(1), 21–37 (2000)
Knuth, D.E.: The Stanford GraphBase: a platform for combinatorial computing, 1st edn. Addison-Wesley, Reading (1993)
Rogers, E.M., Kincaid, D.L.: Communication networks: toward a new paradigm for research, Free Press, USA (1980)
Newman, M.E.J.: Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E 74(3), 036104 (2006)
Hayes, B.: Connecting the dots. Am. Sci. 94(5), 400–404 (2006)
Facebook Netvizz Application. https://apps.facebook.com/netvizz/
Pajek Datasets. http://vlado.fmf.uni-lj.si/pub/networks/data/
Freeman, L.: Datasets. http://moreno.ss.uci.edu/data.html
Borgatti, S.P., Everett, M.G., Johnson, J.C.: Analyzing social networks. 1st edn. SAGE Publications, UK (2013)
Bolland, J.M.: Sorting out centrality: an analysis of the performance of four centrality models in real and simulated networks. Soc. Netw. 10(3), 233–253 (1988)
Rothenberg, R.B., Potterat, J.J., Woodhouse, D.E., Darrow, W.W., Muth, S.Q., Klovdahl, A.S.: Choosing a centrality measure: epidemiologic correlates in the colorado springs study of social networks. Soc. Netw. 17(3-4), 273–297 (1995)
Valente, T.W., Coronges, K., Lakon, C., Costenbader, E.: How correlated are network centrality measures? Connections 28(1), 16–26 (2008)
Barabasi, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509–512 (1999)
de Caen, D.: An upper bound on the sum of squares of degrees in a graph. Discret. Math. 185(1–3), 245–248 (1998)
Goh, K., Oh, E., Jeong, H., Kahng, B., Kim, D.: Classification of scale-free networks. J. Natl. Acad. Sci. USA 99(20), 12583–12588 (2002)
Goh, K., Oh, E., Kahng, B., Kim, D.: Betweenness centrality correlation in social networks. Phys. Rev. E 67(1), 017101 (2003)
Joyce, K.E., Laurienti, P.J., Burdette, J.H., Hayasaka, S.: A new measure of centrality for brain networks. PLoS One 5(8), e12200, 1–13 (2010)
Li, C., Li, Q., Van Mieghem, P., Stanley, H.E., Wang, H.: Correlation between centrality metrics and their application to the opinion model. Eur. Phys. J. B 88(65), 1–13 (2015)
Erdos, P., Renyi, A.: On random graphs I. Publ. Math. 6, 290–297 (1959)