Upgrade to Pro — share decks privately, control downloads, hide ads and more …

7.3節 次数相関の測定 / Measuring Degree Correlations

Yuki Iwanaga
February 27, 2023

7.3節 次数相関の測定 / Measuring Degree Correlations

■7.3節
ネットワークでは,何らかの観点で類似するノード同士がつながっていることがある.
この現象はassortativityと呼ばれ,属性に基づくassortativity(ホモフィリー)と次数に基づくassortativity(次数相関)とに大別できる.
7.3節では,ノードの類似性を次数で測る次数相関関数を定義し,次数相関を一つの指標で表す次数相関指数と次数相関係数を導入する.

■教科書
Barabási, A.-L. (2019)『ネットワーク科学』池田裕一・井上寛康・谷澤俊弘監訳、京都大学ネットワーク社会研究会訳、共立出版
【英語版】http://networksciencebook.com/

■Pythonコード
https://github.com/Nagayu71/NetworkScience-Seminar/tree/main/NetworkScience

Yuki Iwanaga

February 27, 2023
Tweet

More Decks by Yuki Iwanaga

Other Decks in Science

Transcript

  1. "TTPSUBUJWJUZ ࣾձֶɿྨ͸༑ΛݺͿʢIPNPQIJMZʣ ԿΒ͔ͷ؍఺Ͱྨࣅ͍ͯ͠Δϊʔυಉ͕࢜ͭͳ͕͍ͬͯΔ͜ͱ Peter Reid. “Birds of a feather fl

    ock together — collaboration and Svandis”. DataDrivenInvestor. 2018. https://onl.sc/AcC7nyq, ʢࢀর 2023-01-22ʣ w ଐੑʹجͮ͘BTTPSUBUJWJUZ w ࣍਺ʹجͮ͘BTTPSUBUJWJUZ
  2. ଐੑʹجͮ͘BTTPSUBUJWJUZ Zachary's karate club Political blogs network (2004) https://en.wikipedia.org/wiki/Zachary's_karate_club Barabási,

    A.-L. Network science (Cambridge University Press, 2016). http://barabasi.com/networksciencebook/.
  3. ࣍਺ʹجͮ͘BTTPSUBUJWJUZ Menczer, F., Fortunato, S. & Davis, C. A. A

    First Course in Network Science (Cambridge University Press, 2020). Core-periphery-structure Hub-and-spoke
  4. ࣍਺૬ؔߦྻʢઅʣ ϝϦοτ • ࣍਺૬ؔͷ৘ใΛ͢΂ؚͯΉ σϝϦοτ • ղऍ͕೉͍͠ • ߦྻͷαΠζ͕େ͖͘ͳΔ ʹͭΕͯՄࢹԽ͕ࠔ೉

    Barabási, A.-L. Network science (Cambridge University Press, 2016). http://barabasi.com/networksciencebook/.
  5. ྡ઀ϊʔυͷฏۉ࣍਺ ϊʔυ ͷྡ઀ϊʔυͷฏۉ࣍਺ɿ i knn (ki ) = 1 ki

    N ∑ j=1 Aij kj (7.6) A11 … A1j … A1N ⋮ ⋮ ⋮ Ai1 … Aij … AiN ⋮ ⋮ ⋮ AN1 … ANj … ANN ɿྡ઀ߦྻͷཁૉɽ ·ͨ͸ ɽ Aij 0 1 ɿϊʔυ ͷྡ઀ϊʔυͷ࣍਺͚ͩΛՃࢉ͢Δɽ i N ∑ j=1 Aij kj import networks as nx knn_i = nx.average_neighbor_degree(G)
  6. ࣍਺૬ؔؔ਺ͷఆٛ ࣍਺૬ؔؔ਺ʢdegree correlation functionʣΛ࣍ͷΑ͏ʹఆٛ͢Δɿ knn (k) = ∑ k′ 

    k′  P(k′  |k) (7.7) ɿແ࡞ҝʹબΜͩϦϯΫͷยํ͕࣍਺kͷϊʔυͰ͋Δ৔߹ʹɼ΋͏ยํ͕࣍਺k’ͷϊʔυͰ͋Δ֬཰ɽ P(k′  |k) ɿ࣍਺ ͷ͢΂ͯͷϊʔυ ʹؔ͢Δ ͷฏۉɽ knn (k) k i (i = 1,…, n) knn (ki ) ࣍਺૬ؔؔ਺ ࣜͷղऍɿ (7.7) • ࣍਺ ͷϊʔυͷྡ઀ϊʔυ͕ฏۉతʹ࣋ͭฏۉ࣍਺ɽ • ࣍਺ ͷϊʔυ͕༩͑ΒΕͨͱ͖ɼ͍͍ͩͨ ຊͷϦϯΫΛ࣋ͭϊʔυʹғ·Ε͍ͯΔɽ k k knn (k)
  7. χϡʔτϥϧωοτϫʔΫ ࣍਺૬͕ؔͳ͍ ͕ ʹؔͯ͠ҰఆͰ͋ͬͯ΄͍͠ → knn (k) k knn (k)

    = ⟨k2⟩ ⟨k⟩ (7.9) ࣜͷܗΛ໨ࢦͯ͠ɼ৚݅෇͖֬཰ ʢແ࡞ҝʹબΜͩϦϯΫͷยํ͕ 
 ࣍਺kͷϊʔυͰ͋Δ৔߹ʹɼ΋͏ยํ͕࣍਺k’ͷϊʔυͰ͋Δ֬཰ʣΛมܗ͍ͯ͘͠ɽ (7.9) P(k′  |k)
  8.  ࣜͷղऍ (7.9) knn (k) = ⟨k2⟩ ⟨k⟩ (7.9) •

    ࣍਺ ͷϊʔυͷྡ઀ϊʔυ͕ฏۉతʹ࣋ͭฏۉ࣍਺͸ɼ࣍਺ ʹґଘͤͣҰఆͰ͋Δɽ • ࣜ͸ɼϑϨϯυγοϓɾύϥυοΫεʢฏۉతʹࣗ෼ͷ༑ୡ͸ࣗ෼ΑΓ΋ଟ͘ͷ༑ୡΛ 
 ࣋ͭʣΛ͍ࣔͯ͠Δɽ k k (7.9) ⟨k2⟩ ⟨k⟩
  9. /FUXPSL9ʹΑΔ࣮૷ import networks as nx # G: graph object def

    get_k_knn(G): knn_dict = nx.k_nearest_neighbors(G) return list(knn_dict.keys()), list(knn_dict.values()) Before NetworkX v3.0 NetworkX v3.0 import networks as nx # G: graph object def get_k_knn(G): knn_dict = nx.average_degree_connectivity(G) return list(knn_dict.keys()), list(knn_dict.values())
  10. ૬ؔࢦ਺μ ࣍਺૬ؔؔ਺ ͸࣍ͷ ࣜʹΑͬͯۙࣅͰ͖ɼ૬ؔͷ༗ແΛ૬ؔࢦ਺ Ͱ֬ೝͰ͖Δɽ knn (k) (7.10) μ knn

    (k) = akμ (7.10) log knn (k) = log a + μ log k (7.10′  ) ૬ؔͷ༗ແͷ൑அ w ࣍਺਌࿨తωοτϫʔΫͷ৔߹ɿ  w χϡʔτϥϧωοτϫʔΫͷ৔߹ɿ  w ࣍਺ഉଞతͳωοτϫʔΫͷ৔߹ɿ μ > 0 μ = 0 μ < 0
  11. ૬ؔࢦ਺ ͷਪఆʢ0-4ʣ μ log knn (k) = log a +

    μ log k (7.10′  ) μ = − 0.23 a = exp(6.77) μ = 0.22 a = exp(2.68)
  12. ࣍਺૬ؔ܎਺r ແ࡞ҝʹબΜͩϦϯΫͷ྆୺ʹ͋Δϊʔυͷ࣍਺ʢ֬཰ม਺ ͱ ʣͷ૬ؔ܎਺ j k ૬ؔͷ༗ແͷ൑அ w ࣍਺਌࿨తωοτϫʔΫͷ৔߹ɿ 

    w χϡʔτϥϧωοτϫʔΫͷ৔߹ɿ  w ࣍਺ഉଞతͳωοτϫʔΫͷ৔߹ɿ r > 0 r = 0 r < 0 (7.11) (7.12)
  13. ϐΞιϯͷ૬ؔ܎਺ ϐΞιϯͷ฼૬ؔ܎਺ʢpopulation Pearson correlation coefficientʣ͸࣍ͷΑ͏ʹఆٛ͞ΕΔɽ ρX,Y = Cov(X, Y) σX

    σY Cov(X, Y) = E[(X − E[X])(Y − E[Y])] = E[XY] − E[X]E[Y], ͜͜Ͱɼ ˡڞ෼ࢄ ˡඪ४ภࠩͷੵ σ2 X = E[X2] − (E[X])2, σ2 Y = E[Y2] − (E[Y])2 .
  14. /FUXPSL9ʹΑΔ࣮૷ ૬ؔͷ༗ແͷ൑அ w ࣍਺਌࿨తωοτϫʔΫͷ৔߹ɿ  w χϡʔτϥϧωοτϫʔΫͷ৔߹ɿ  w ࣍਺ഉଞతͳωοτϫʔΫͷ৔߹ɿ

    r > 0 r = 0 r < 0 import networks as nx import scipy as sp # for pearson correlation r = nx. degree_assortativity_coefficient(G) #r = nx. degree_pearson_correlation_coefficient(G)