Webgrafía

Gráfico de páginas web conectadas

El webgrafo describe los enlaces dirigidos entre páginas de la World Wide Web . Un grafo , en general, consta de varios vértices, algunos pares conectados por aristas. En un grafo dirigido , las aristas son líneas o arcos dirigidos. El webgrafo es un grafo dirigido, cuyos vértices corresponden a las páginas de la WWW, y una arista dirigida conecta la página X con la página Y si existe un hipervínculo en la página X, que haga referencia a la página Y.

Propiedades

• La distribución de grados del webgrafo difiere fuertemente de la distribución de grados del modelo de grafo aleatorio clásico, el modelo de Erdős–Rényi : ^[1] en el modelo de Erdős–Rényi, hay muy pocos nodos de grado grandes, en relación con la distribución de grados del webgrafo. La distribución precisa no está clara, ^[2] sin embargo: está relativamente bien descrita por una distribución lognormal , así como por el modelo de Barabási–Albert para leyes de potencia . ^{[3] [4]}
• El webgraph es un ejemplo de una red libre de escala .

Aplicaciones

El webgraph se utiliza para:

• calcular el PageRank ^[5] de las páginas WWW;
• calcular el PageRank personalizado; ^[6]
• detección de páginas web de temas similares, únicamente a través de propiedades grafo-teóricas, como la co-cita; ^[7]
• e identificar centros y autoridades en la web para el algoritmo HITS .

Referencias

1. P. Erdős, A. Renyi, Publ. Matemáticas. Inst. Colgado. Acad. Ciencia. 5 (1960)
2. Meusel, R.; Vigna, S.; Lehmberg, O.; Bizer, C. (2015). "La estructura de grafos en la Web: analizada en diferentes niveles de agregación" (PDF) . Journal of Web Science . 1 (1): 33–47. doi :10.1561/106.00000003. hdl : 2434/372411 .
3. Clauset, A.; Shalizi, CR; Newman, MEJ (2009). "Distribuciones de ley de potencia en datos empíricos". SIAM Rev . 51 (4): 661–703. arXiv : 0706.1062 . Código Bibliográfico :2009SIAMR..51..661C. doi :10.1137/070710111. S2CID  9155618.
4. Barabási, Albert-László; Albert, Réka (octubre de 1999). "Aparición del escalado en redes aleatorias" (PDF) . Ciencia . 286 (5439): 509–512. arXiv : cond-mat/9910332 . Código Bib : 1999 Ciencia... 286.. 509B. doi : 10.1126/ciencia.286.5439.509. PMID  10521342. S2CID  524106..
5. S. Brin , L. Page , Redes informáticas y sistemas RDSI 30, 107 (1998)
6. Glen Jeh y Jennifer Widom. 2003. Escalado de la búsqueda web personalizada. En Actas de la 12.ª conferencia internacional sobre la World Wide Web (WWW '03). ACM, Nueva York, NY, EE. UU., 271–279. doi :10.1145/775152.775191
7. Kumar, Ravi; Raghavan, Prabhakar; Rajagopalan, Sridhar; Tomkins, Andrew (1999). "Buscando cibercomunidades emergentes en la Web". Redes informáticas . 31 (11–16): 1481–1493. CiteSeerX 10.1.1.89.4025 . doi :10.1016/S1389-1286(99)00040-7. S2CID  7069190. 

Enlaces externos

• Webgraphs en Yahoo Sandbox
• Webgraphs en la Universidad de Milán: laboratorio de algorítmica web
• Webgraphs en Stanford – SNAP
• Webgraph en el servidor Webgraph de Erdős
• Web Data Commons - Gráfico de hipervínculos