4 votos

Pruebas de hipótesis de mayor densidad en subconjuntos de una red/grafo

Tengo una red con más de 40k nodos y unos 12 millones de aristas (pesos flotantes) y tengo unos 10k subconjuntos de esta red que quiero probar para aumentar la densidad.

Se me ocurren las siguientes opciones:

  1. Binarizar la red y formar el problema como una prueba chi cuadrado de densidad local (subregión) frente a la densidad global de la red. Por binarización me refiero a aristas con pesos 1 o 0 (arista existente o no).

    Desventaja : tienen que binarizar la red y requiere establecer un magia umbral de eliminación/mantenimiento de bordes.

    Ventajas : Computacionalmente más barato que la segunda opción.

  2. Evite binarizar y realice la prueba ranksum entre el peso de los bordes de la red local frente a la global

    Desventaja En el caso de las subregiones con pocas aristas de peso alto, con muchas aristas de peso medio o con ambas, es difícil decidir si una subregión está significativamente enriquecida.

    Ventaja : no magia umbral.

Necesitaría realizar muchas permutaciones y utilizar un procedimiento de control FWER o FDR, por lo que probablemente la primera opción sea mejor que la segunda, pero realmente no me gusta la idea del corte mágico.

¿Hay alguna otra forma mejor de enfocar esto?

1voto

richard bradford Puntos 1

La mera observación de la densidad global de pesos o de la distribución de pesos, respectivamente, corresponde a la hipótesis nula de que no existe estructura alguna en la red y las aristas se asignan aleatoriamente. Por ejemplo, esta hipótesis nula implica que su red no contiene hubs, es decir, nodos que presentan más conexiones o conexiones más fuertes de las que cabría esperar por azar. Como ha descrito su aplicación, esta hipótesis nula es errónea . Por ejemplo, una de sus subredes puede mostrar una densidad de enlaces significativamente alta según esta hipótesis nula sólo porque contiene un nudo más que una subred aleatoria de este tamaño, mientras que no sería significativa según una hipótesis nula más adecuada que tenga en cuenta la presencia de nudos.

Aunque un modelo nulo de este tipo es tedioso y a menudo imposible de describir analíticamente, a menudo se pueden obtener fácilmente instancias de este modelo nulo (sustitutos) mediante algún tipo de bootstrapping : En el caso más sencillo, estos sustitutos serían subredes formadas por $n$ nodos aleatorios, donde $n$ es el número de nodos de la subred que desea investigar. Nótese que lo que propongo son sustitutos para subredes, no para toda la red (que no cambiaría). También hay que tener en cuenta que si se tiene algún conocimiento a priori sobre las subredes, por ejemplo, que todas están conectadas, los sustitutos también deben elegirse de acuerdo con este conocimiento a priori (lo que puede ser difícil). No estoy del todo seguro de si esto se aplica a su aplicación.

Una vez que tenga sus subredes sustitutivas, todo lo que tiene que hacer es comparar sus densidades de enlaces con las de las subredes que realmente quiere investigar. Por ejemplo, si la densidad de enlaces de su subred original (o la medida que desee) es superior a la de $m=19$ sustitutos de subred, su subred tiene una densidad de enlaces significativamente alta con $p=0.05=\tfrac{1}{m+1}$ ‡ . No veo ninguna ventaja en la binarización cuando se sigue este procedimiento. Incluso si se opta por tener 10.000 sustitutos (que es más de lo que normalmente se necesita) y todas las subredes originales tienen el mismo tamaño, el coste computacional es el mismo que evaluar las 10.000 subredes originales (generar sustitutos puede ser más costoso). (aunque generar los sustitutos puede ser más caro si hay que tener en cuenta conocimientos previos).

‡ para obtener informaci-n detallada sobre las estad'sticas de los sustitutos, v'ase, por ejemplo, la secci-n 3.3 de Documento de Schreiber y Schmitz sobre sustitutos de series temporales ( Arxiv )

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X