Ves esta página sin formato porque esta hecha cumpliendo el estándar web CSS 2.
Tu navegador no soporta este estándar, o tienes dicho soporte desactivado.
si estas en el primer caso, actualízate. merece mucho la pena.

Una aventura personal hacia las redes complejas.


Inicio > Historias > Bitácoras y grafos n-partitos

2005-08-30

Bitácoras y grafos n-partitos

Por malambo en Invariancia.General | 2005-08-30


El 21 de agosto, en una entrada de la que también se hace eco JJ, Fernado Plaza decía en su bitácora:

"Actualmente estoy suscrito a 73 feeds y ninguno de mis suscriptores con perfiles públicos está suscritos a menos de 50."

Aquí hay, por lo menos, dos conjuntos disjuntos de ítems: Los suscriptores y las bitácoras, aunque la partición podría extenderse también a los feeds. Para representar esta situación con un grafo es posible recurrir a las redes n-partitas.

Grafo bipartito

Sea G=<N, C> un grafo. Sean N1 y N2 subconjuntos no vacíos de N tales que su intersección es vacía y su unión es N. G es un grafo bipartito si y sólo si todo conector <i, j> en C es tal que i pertenece a N1 y j pertenece a N2


En nuestro caso N1 son las bitácoras y N2 los suscriptores. De la misma forma, si es posible hacer una división en tres subconjuntos no vacíos N1, N2 y N3 de manera que los nodos en el mismo subconjunto no estén conectados entre sí, entonces tendremos un grafo tripartito. Esta idea puede extenderse a n conjuntos disjuntos tales que dentro de cada uno de ellos no existan nodos adyacentes (dos nodos son adyacentes si están conectados).

Proyección

Dada una red bipartita siempre es posible proyectarla sobre una red unipartita. Por ejemplo, para deteminar comunidades de científicos es usual recurrir a las bases de datos en las que figuran los papers (la bases arXiv o BioMed Central son ejemplos) y crear un grafo en el que N1 es el conjunto de los papers y N2 el conjunto de los científicos. Un científico estará vinculado con un paper si es su autor. A partir de este grafo puede obtenerse otro (una proyección) cuya composición estará constituida únicamente por científicos (o papers, el problema es simétrico). Dos científicos estarán conectados en este nuevo grafo si alguna vez escribieron juntos un artículo.

Para el caso de las bitácoras proyecciones de este tipo tienen poca utilidad, dado que el hecho de que dos lectores visiten una página no establece ningún vínculo entre ellos. Sin embargo, si un grupo de personas visita más o menos las mismas bitácoras es posible que formen parte de alguna comunidad y lo mismo para las bitácoras, si dos de ellas son visitadas por el mismo grupo de lectores es probable que exista algún hipervínculo que las enlace.

A partir de una red bipartita es posible establecer una función que determine la probabilidad que dos personas se conozcan (que hayan establecido algún tipo de contacto) o, dado que el problema es simétrico, la probabilidad de que dos bitácoras estén enlazadas por un hipervínculo. Esta probabilidad no tiene por qué coincidir con la estructura real de la blogosfera, porque los autores no están obligados a saber que cosas leen sus visitantes ni a obrar en consecuencia; no obstante, sospecho que tal probabilidad debe ser un parámetro importante a tener en cuenta a la hora de analizar y predecir la evolución de la red (al fin y al cabo, los autores también somos asiduos lectores de otras bitácoras).

Una forma de determinar esa función de probabilidad es considerar, como lo hicieron Petter Holme et al. al estudiar la vida de una universidad Coreana, la probabilidad de que dos nodos estén relacionados como el conector ponderado que los vincula. Si nk es la cantidad de visitantes que tiene la bitácora k, entonces su contribución a la probabilidad de que los lectores i y j se conozcan será 1/nk (cuanto más lectores tenga una bitácora, menor es la probabilidad de que dos de ellos establezcan un contacto). Pero por otra parte, cuanto más bitácoras tengan en común dos personas, mayor será la probabilidad de que se conozcan.

Por lo tanto, la probabilidad de que i conozca a j es

w(i, j) = Σk δk(i, j)/nk

(1)



donde la suma se realiza sobre el conjunto de todas las bitácoras y δk(i, j) = 1 sólo si i y j (distintos) visitan k y cero en otro caso. Lo mismo, pero extendiendo la suma sobre los visitantes, puede hacerse para calcular la probabilidad de enlace entre las bitácoras.


2005-08-30 20:48 | 0 Comentarios


Referencias (TrackBacks)

URL de trackback de esta historia http://invariancia.blogalia.com//trackbacks/32593

Comentarios

portada | subir

(CC) 2005-2006 - malambo