그래프의 편향된 랜덤 워크

네트워크 과학에서, 그래프에서 편향된 랜덤 워크는 진화하는 변수가 현재 상태에서 다양한 잠재적 새로운 상태 중 하나로 점프하는 시간 경로 과정이다. 순수 랜덤 워크와 달리 잠재적인 새로운 상태의 확률은 동일하지 않다.

그래프의 편향된 랜덤 워크는 네트워크가 너무 복잡하거나 통계적 방법으로 분석할 수 있을 만큼 충분히 크지 않은 경우 대칭을 추출하기 위해 무방향 그래프의 구조적 분석에 대한 접근방식을 제공한다.그래프에서 편향된 랜덤 워크의 개념은 특히 교통 및 소셜 네트워크에서 ^[1]지난 10년 동안 많은 연구자와 데이터 회사의 관심을 끌었다.

모델

분석의 특정 목적에 기초한 그래프에 편향된 랜덤 워크의 많은 다른 표현이 있었다.무방향 그래프에 대한 메커니즘의 일반적인 표현은 다음과 같습니다.^[2]

무방향 그래프에서 워커는 현재 $노드$ j $,$ {\ $displaystyle$ j $,}$ 에서 $j,$ $i.$ $노드$ i로 한 걸음 이동합니다 $.$ 각 노드에 $\alpha _{i},$ i $,$ {\ $displaystyle \alpha$ _ ${i$ $}$ 가 $\alpha _{i},$ 있다고 가정하면 $노드$ j {\ $displaystyle$ j $}$ 에서 $j$ $i$ 로 $i$ 점프할 확률은 다음과 같습니다.

T_{ij}^{\alpha} = frac {alpha _{i}A_{ij}}{\sum _{k}\alpha _{k}A_{kj}}},

$A_{ij}$ 서 a j $({$ 는 $A_{ij}$ j $(style$ j $)$ 에서 $j$ i $(style$ i $)$ 로 이어지는 가장자리의 토폴로지적인 가중치를 나타냅니다. $}$

실제로 워커의 스텝은 노드마다 다를 수 있는 $\alpha$ α $(\displaystyle$ \^[3]alpha $)$ $\alpha$ 에 의해 편향됩니다.

네트워크에 따라 $(\display\alpha)$ 를 $\alpha$ 다르게 해석할 수 있습니다.그것은 소셜 네트워크에서의 개인의 매력으로 암시될 수도 있고, 그 사이의 중심성일 수도 있고, 심지어 노드의 본질적인 특성으로 설명될 수도 있다. $(\displaystyle \alpha})$ 에서 $\alpha$ 균등하게 랜덤 워크하는 경우 모든 노드에 대해 1개입니다.

최단 패스의 경우 랜덤^[4] $\alpha _{i}$ i\ $\alpha _{i}$ $displaystyle$ $\alpha _{i}$ \ $alpha$ _ { $\alpha _{i}$ i $i$ }는 $\alpha _{i}$ $노드$ $i$ 를 통과하는 모든 노드 쌍 사이의 최단 패스의 총수입니다.실제로 워커는 다음과 같이 정의되어 있는 노드간의 중심성이 높은 노드를 선호합니다.

C(i)=tfrac {{\text}}}i}{\text{를 통과하는 총 최단 경로 수총 최단 경로 수}}}}

위의 방정식에 기초하여 바이어스 워크의 노드에 대한 반복 시간은 다음과 같이 ^[5]구한다.

r_{i}=black {1}{C(i)}

적용들

그래프에서 편향된 랜덤 워크를 사용하는 다양한 애플리케이션이 있다.확산 억제, 소셜 ^[7]네트워크 ^[6]상품 광고, 동물·미생물 분산·인구 ^[8]재분배 설명, 커뮤니티 탐지,^[9] 무선 네트워크,^[10] 검색 ^[11]엔진 등이 해당된다.

「」를 참조해 주세요.

레퍼런스

^ Roberta Sinatra, Jesús Gómez-Gardeñes, Renaud Lambiotte, Vincenzo Nicosia, and Vito Latora (March 2011). "Maximal-entropy random walks in complex networks with limited information". Physical Review E. 83 (3): 030103. arXiv:1007.4936. Bibcode:2011PhRvE..83c0103S. doi:10.1103/PhysRevE.83.030103. PMID 21517435. S2CID 6984660.{{cite journal}}: CS1 maint: 작성자 파라미터 사용(링크)
^ J. Gómez-Gardeñes; V. Latora (Dec 2008). "Entropy rate of diffusion processes on complex networks". Physical Review E. 78 (6): 065102. arXiv:0712.0278. Bibcode:2008PhRvE..78f5102G. doi:10.1103/PhysRevE.78.065102. PMID 19256892. S2CID 14100937.
^ R. Lambiotte, R. Sinatra, J.-C. Delvenne, T.S. Evans, M. Barahona, V. Latora (Dec 2010). "Flow graphs: interweaving dynamics and structure". Physical Review E. 84 (1): 017102. arXiv:1012.1211. Bibcode:2011PhRvE..84a7102L. doi:10.1103/PhysRevE.84.017102. PMID 21867345. S2CID 2286264.{{cite journal}}: CS1 maint: 작성자 파라미터 사용(링크)
^ Blanchard, Volchenkov, D (2008). Mathematical Analysis of Urban Spatial Networks. Understanding Complex Systems. doi:10.1007/978-3-540-87829-2. ISBN 978-3-540-87828-5.{{cite book}}: CS1 maint: 작성자 파라미터 사용(링크)
^ Volchenkov D; Blanchard P (2011). Fair and biased random walks on undirected graphs and related entropies. Birkhäuser. p. 380. ISBN 9780817649036.
^ Chung, Zhao, Fan, Wenbo (2010). "PageRank and random walks on graphs". Fete of Combinatorics and Computer Science. Bolyai Society Mathematical Studies. Vol. 20. pp. 43–62. CiteSeerX 10.1.1.157.7116. doi:10.1007/978-3-642-13580-4_3. ISBN 978-3-642-13579-8. {{cite book}}:누락 또는 비어 있음 title=(도움말)
^ Adal, K.M. (June 2010). "Biased random walk based routing for mobile ad hoc networks". 2010 International Conference on Intelligent and Advanced Systems. pp. 1–6. doi:10.1109/ICIAS.2010.5716181. ISBN 978-1-4244-6623-8. S2CID 16113377.
^ Kakajan Komurov, Michael A. White, Prahlad T. Ram (Aug 2010). "Use of Data-Biased Random Walks on Graphs for the Retrieval of Context-Specific Networks from Genomic Data". PLOS Comput Biol. 6 (8): e1000889. Bibcode:2010PLSCB...6E0889K. doi:10.1371/journal.pcbi.1000889. PMC 2924243. PMID 20808879.{{cite journal}}: CS1 maint: 작성자 파라미터 사용(링크)
^ J.K. Ochab; Z. Burda (Jan 2013). "Maximal entropy random walk in community detection". The European Physical Journal Special Topics. 216: 73–81. arXiv:1208.3688. Bibcode:2013EPJST.216...73O. doi:10.1140/epjst/e2013-01730-6. S2CID 56409069.
^ Beraldi, Roberto (Apr 2009). "Biased Random Walks in Uniform Wireless Networks". IEEE Transactions on Mobile Computing. 8 (4): 500–513. doi:10.1109/TMC.2008.151. S2CID 13521325.
^ Da-Cheng Nie, Zi-Ke Zhang, Qiang Dong, Chongjing Sun,Yan Fu (July 2014). "Information Filtering via Biased Random Walk on Coupled Social Network". The Scientific World Journal. 2014: 829137. doi:10.1155/2014/829137. PMC 4132410. PMID 25147867.{{cite journal}}: CS1 maint: 작성자 파라미터 사용(링크)

외부 링크

가보르 시몬이 "그래프 엔트로피: 조사"조합 최적화(ed)W. Cook, L. Lovasz, P.시모어)프로비던스, 아머수학. Soc., 399-441, 1995년 페이지
Anne-Marie Kermarrec, Erwan Le Merrer, Bruno Sericola, Gilles Trédan, Gadi Taubenfelt의 "랜덤 워크를 통한 네트워크 토폴로지의 품질 평가" (ed.)

[1] Roberta Sinatra, Jesús Gómez-Gardeñes, Renaud Lambiotte, Vincenzo Nicosia, and Vito Latora (March 2011). "Maximal-entropy random walks in complex networks with limited information". Physical Review E. 83 (3): 030103. arXiv:1007.4936. Bibcode:2011PhRvE..83c0103S. doi:10.1103/PhysRevE.83.030103. PMID 21517435. S2CID 6984660.{{cite journal}}: CS1 maint: 작성자 파라미터 사용(링크)

[2] J. Gómez-Gardeñes; V. Latora (Dec 2008). "Entropy rate of diffusion processes on complex networks". Physical Review E. 78 (6): 065102. arXiv:0712.0278. Bibcode:2008PhRvE..78f5102G. doi:10.1103/PhysRevE.78.065102. PMID 19256892. S2CID 14100937.

[3] R. Lambiotte, R. Sinatra, J.-C. Delvenne, T.S. Evans, M. Barahona, V. Latora (Dec 2010). "Flow graphs: interweaving dynamics and structure". Physical Review E. 84 (1): 017102. arXiv:1012.1211. Bibcode:2011PhRvE..84a7102L. doi:10.1103/PhysRevE.84.017102. PMID 21867345. S2CID 2286264.{{cite journal}}: CS1 maint: 작성자 파라미터 사용(링크)

[4] Blanchard, Volchenkov, D (2008). Mathematical Analysis of Urban Spatial Networks. Understanding Complex Systems. doi:10.1007/978-3-540-87829-2. ISBN 978-3-540-87828-5.{{cite book}}: CS1 maint: 작성자 파라미터 사용(링크)

[5] Volchenkov D; Blanchard P (2011). Fair and biased random walks on undirected graphs and related entropies. Birkhäuser. p. 380. ISBN 9780817649036.

[6] Chung, Zhao, Fan, Wenbo (2010). "PageRank and random walks on graphs". Fete of Combinatorics and Computer Science. Bolyai Society Mathematical Studies. Vol. 20. pp. 43–62. CiteSeerX 10.1.1.157.7116. doi:10.1007/978-3-642-13580-4_3. ISBN 978-3-642-13579-8. {{cite book}}:누락 또는 비어 있음 title=(도움말)

[7] Adal, K.M. (June 2010). "Biased random walk based routing for mobile ad hoc networks". 2010 International Conference on Intelligent and Advanced Systems. pp. 1–6. doi:10.1109/ICIAS.2010.5716181. ISBN 978-1-4244-6623-8. S2CID 16113377.

[8] Kakajan Komurov, Michael A. White, Prahlad T. Ram (Aug 2010). "Use of Data-Biased Random Walks on Graphs for the Retrieval of Context-Specific Networks from Genomic Data". PLOS Comput Biol. 6 (8): e1000889. Bibcode:2010PLSCB...6E0889K. doi:10.1371/journal.pcbi.1000889. PMC 2924243. PMID 20808879.{{cite journal}}: CS1 maint: 작성자 파라미터 사용(링크)

[9] J.K. Ochab; Z. Burda (Jan 2013). "Maximal entropy random walk in community detection". The European Physical Journal Special Topics. 216: 73–81. arXiv:1208.3688. Bibcode:2013EPJST.216...73O. doi:10.1140/epjst/e2013-01730-6. S2CID 56409069.

[10] Beraldi, Roberto (Apr 2009). "Biased Random Walks in Uniform Wireless Networks". IEEE Transactions on Mobile Computing. 8 (4): 500–513. doi:10.1109/TMC.2008.151. S2CID 13521325.

[11] Da-Cheng Nie, Zi-Ke Zhang, Qiang Dong, Chongjing Sun,Yan Fu (July 2014). "Information Filtering via Biased Random Walk on Coupled Social Network". The Scientific World Journal. 2014: 829137. doi:10.1155/2014/829137. PMC 4132410. PMID 25147867.{{cite journal}}: CS1 maint: 작성자 파라미터 사용(링크)

[1]

[2]

[3]

[4]

[5]

[7]

[6]

[8]

[9]

[10]

[11]

Search

그래프의 편향된 랜덤 워크

네임스페이스

더

목차

모델

적용들

「」를 참조해 주세요.

레퍼런스

외부 링크

Search

그래프의 편향된 랜덤 워크

모델

적용들

「 」를 참조해 주세요.

레퍼런스

외부 링크

「」를 참조해 주세요.