Hispanopedia Wiki
Articulo de referencia

Predicción de enlaces

En la teoría de redes , la predicción de enlaces es el problema de predecir la existencia de un enlace entre dos entidades en una red. Ejemplos de predicción de enlaces incluyen...

Hispanopedia WikiContenido en espanolLectura gratuita

En la teoría de redes , la predicción de enlaces es el problema de predecir la existencia de un enlace entre dos entidades en una red. Ejemplos de predicción de enlaces incluyen la predicción de enlaces de amistad entre usuarios en una red social , la predicción de enlaces de coautoría en una red de citas y la predicción de interacciones entre genes y proteínas en una red biológica . La predicción de enlaces también puede tener un aspecto temporal, donde, dada una instantánea del conjunto de enlaces en un momento dado,t{\displaystyle t}, el objetivo es predecir los vínculos en el tiempot+1{\displaystyle t+1}La predicción de enlaces tiene una amplia aplicabilidad. En el comercio electrónico, suele ser una tarea secundaria para recomendar artículos a los usuarios. En la gestión de bases de datos de citas, se puede utilizar para eliminar registros duplicados. En bioinformática, se ha utilizado para predecir interacciones proteína-proteína (PPI). También se utiliza para identificar grupos ocultos de terroristas y delincuentes en aplicaciones relacionadas con la seguridad. [ 1 ]

Definición del problema

Consideremos una redGRAMO=(V,mi){\displaystyle G=(V,E)}, dóndeV{\displaystyle V}representa los nodos de entidad en la red ymi⊆|V|{\displaystyle E\subseteq |V|}incógnita|V|{\displaystyle |V|}representa el conjunto de enlaces "verdaderos" entre entidades en la red. Se nos da el conjunto de entidades.V{\displaystyle V}y un subconjunto de enlaces verdaderos que se denominan enlaces observados . El objetivo de la predicción de enlaces es identificar los enlaces verdaderos no observados. En la formulación temporal de la predicción de enlaces, los enlaces observados corresponden a los enlaces verdaderos en un momento dado.t{\displaystyle t}y el objetivo es inferir el conjunto de enlaces verdaderos en el momentot+1{\displaystyle t+1} Por lo general, también se nos proporciona un subconjunto de enlaces no observados llamados enlaces potenciales.mi′{\displaystyle E'}y necesitamos identificar los vínculos reales entre estos vínculos potenciales.

En la formulación de clasificación binaria de la tarea de predicción de enlaces, los enlaces potenciales se clasifican como enlaces verdaderos o enlaces falsos. Los enfoques de predicción de enlaces para este entorno aprenden un clasificador.METROb{\displaystyle M_{b}}que mapea enlaces enmi′{\displaystyle E'}a etiquetas positivas y negativas, es decirMETROb:mi′→{0,1}{\displaystyle M_{b}:E'\to \{0,1\}}En la formulación de estimación de probabilidad, los enlaces potenciales se asocian con probabilidades de existencia. Los enfoques de predicción de enlaces para este entorno aprenden un modelo.METROpag{\displaystyle M_{p}}que mapea enlaces enmi′{\displaystyle E'}a una probabilidad, es decirMETROpag:mi′→[0,1]{\displaystyle M_{p}:E'\to [0,1]}.

Los métodos de enlace único aprenden un modelo que clasifica cada enlace de forma independiente. Los métodos de predicción estructurada capturan la correlación entre los enlaces potenciales formulando la tarea como una tarea de predicción de enlaces colectivos. Los métodos de predicción de enlaces colectivos aprenden un modelo que identifica conjuntamente todos los enlaces verdaderos entre el conjunto de enlaces potenciales.

La tarea de predicción de enlaces también puede formularse como un ejemplo de estimación de valores faltantes. En este caso, el grafo se representa como una matriz de adyacencia con valores faltantes. La tarea consiste en completar la matriz identificando dichos valores. Los métodos basados ​​en la factorización de matrices suelen utilizar esta formulación.

Historia

La tarea de predicción de enlaces ha atraído la atención de varias comunidades de investigación que abarcan desde la estadística y la ciencia de redes hasta el aprendizaje automático y la minería de datos . En estadística, los modelos de grafos aleatorios generativos, como los modelos de bloques estocásticos, proponen un enfoque para generar enlaces entre nodos en un grafo aleatorio . Para las redes sociales, Liben-Nowell y Kleinberg propusieron modelos de predicción de enlaces basados ​​en diferentes medidas de proximidad de grafos. [ 2 ] La comunidad de aprendizaje automático y minería de datos ha propuesto varios modelos estadísticos para la predicción de enlaces. Por ejemplo, Popescul et al. propusieron un modelo de regresión logística estructurada que puede utilizar características relacionales. [ 3 ] O'Madadhain et al. propusieron modelos de probabilidad condicional local basados ​​en atributos y características estructurales. [ 4 ] Getoor propuso varios modelos basados ​​en modelos gráficos dirigidos para la predicción colectiva de enlaces. [ 5 ] También se han propuesto otros enfoques basados ​​en paseos aleatorios. [ 6 ] y factorización de matrices. [ 7 ] Con el advenimiento del aprendizaje profundo, también se han propuesto varios enfoques basados ​​en incrustaciones de grafos para la predicción de enlaces. [ 8 ] Para obtener más información sobre la predicción de enlaces, consulte el estudio de Getoor et al. [ 9 ] y Yu et al. [ 10 ]

Enfoques y métodos

Se han propuesto varios enfoques de predicción de enlaces, incluyendo enfoques no supervisados ​​como medidas de similitud calculadas sobre los atributos de las entidades, enfoques basados ​​en paseos aleatorios y factorización de matrices , y enfoques supervisados ​​basados ​​en modelos gráficos y aprendizaje profundo . Los enfoques de predicción de enlaces se pueden dividir en dos grandes categorías según el tipo de red subyacente: (1) enfoques de predicción de enlaces para redes homogéneas y (2) enfoques de predicción de enlaces para redes heterogéneas. Según el tipo de información utilizada para predecir enlaces, los enfoques se pueden clasificar como enfoques basados ​​en topología, enfoques basados ​​en contenido y métodos mixtos. [ 11 ]

Métodos basados ​​en la topología

Los métodos basados ​​en la topología parten de la premisa de que los nodos con una estructura de red similar tienen más probabilidades de formar un enlace.

vecinos comunes

Este es un método común para predecir enlaces que calcula el número de vecinos comunes . Las entidades con más vecinos en común tienen mayor probabilidad de tener un enlace. Se calcula de la siguiente manera:

donorte(A,B)=|A∩B|{\displaystyle CN(A,B)={|A\cap B|}}

Una desventaja de este enfoque es que no tiene en cuenta el número relativo de vecinos comunes.

Medida de Jaccard

La medida de Jaccard aborda el problema de los vecinos comunes calculando el número relativo de vecinos en común:

J(A,B)=|A∩B||A∪B|{\displaystyle J(A,B)={{|A\cap B|} \over {|A\cup B|}}}

Medida de Adamic-Adar

La medida de Adamic-Adar [ 12 ] es la suma del logaritmo de la intersección de los vecinos de dos nodos. Esto captura una similitud de dos saltos, que puede producir mejores resultados que los métodos simples de un salto. Se calcula de la siguiente manera:

A(incógnita,y)=∑tú∈norte(incógnita)∩norte(y)1registro⁡|norte(tú)|,{\displaystyle A(x,y)=\sum _{u\in N(x)\cap N(y)}{\frac {1}{\log |N(u)|}},}

dóndenorte(tú){\displaystyle N(u)}es el conjunto de nodos adyacentes atú{\displaystyle u}.

Medida de Katz

Los métodos basados ​​en vecinos pueden ser efectivos cuando el número de vecinos es grande, pero este no es el caso en grafos dispersos. En estas situaciones es apropiado utilizar métodos que tengan en cuenta recorridos más largos. La medida de Katz [ 13 ] es una métrica que captura esto. Se calcula buscando en el grafo caminos de longitudt{\displaystyle t}en el gráfico y sumando los recuentos de cada longitud de ruta ponderada por pesos especificados por el usuario.

Sea A la matriz de adyacencia de la red en consideración. Elementos(aij){\displaystyle (a_{ij})}Las potencias de A son variables que toman un valor de 1 si un nodo i está conectado al nodo j y 0 en caso contrario. Las potencias de A indican la presencia (o ausencia) de enlaces entre dos nodos a través de intermediarios. Por ejemplo, en la matrizA3{\displaystyle A^{3}}, si el elemento(a2,12)=1{\displaystyle (a_{2,12})=1}, indica que el nodo 2 y el nodo 12 están conectados a través de un camino de longitud 3. SidoKatz(i){\displaystyle C_{\mathrm {Katz} }(i)}denota la centralidad de Katz de un nodo i , entonces matemáticamente: 

doKatz(i)=∑k=1∞∑j=1norteαk(Ak)ji{\displaystyle C_{\mathrm {Katz} }(i)=\sum _ {k=1}^{\infty }\sum _ {j=1}^{n}\alpha ^{k}(A^{k})_{ji}}

Tenga en cuenta que la definición anterior utiliza el hecho de que el elemento en la ubicación(i,j){\displaystyle (i,j)}deAk{\displaystyle A^{k}}refleja el número total dek{\displaystyle k}conexiones de grado entre nodosi{\displaystyle i}yj{\displaystyle j}.

Métodos basados ​​en atributos de nodo

Los métodos de similitud de nodos predicen la existencia de un enlace basándose en la similitud de los atributos de los nodos.

distancia euclidiana

Los valores de los atributos se representan como un vector normalizado y la distancia entre los vectores se utiliza para medir la similitud. Distancias pequeñas indican mayor similitud.

similitud del coseno

Tras normalizar los valores de los atributos, calcular el coseno entre los dos vectores es una buena medida de similitud, donde los valores más altos indican una mayor similitud.

Métodos mixtos

Los métodos mixtos combinan métodos basados ​​en atributos y en topología.

Incrustaciones de grafos

Las incrustaciones de grafos también ofrecen una forma práctica de predecir enlaces. [ 8 ] Los algoritmos de incrustación de grafos, como Node2vec , aprenden un espacio de incrustación en el que los nodos vecinos se representan mediante vectores, de modo que las medidas de similitud vectorial, como la similitud del producto escalar o la distancia euclidiana, se mantienen en dicho espacio. Estas similitudes dependen tanto de las características topológicas como de la similitud basada en atributos. Posteriormente, se pueden utilizar otras técnicas de aprendizaje automático para predecir aristas a partir de la similitud vectorial.

Modelos de relaciones probabilísticas

Un modelo relacional probabilístico (MRP) especifica una plantilla para una distribución de probabilidad sobre bases de datos. La plantilla describe el esquema relacional del dominio y las dependencias probabilísticas entre los atributos del dominio. Un MRP, junto con una base de datos particular de entidades y enlaces no observados, define una distribución de probabilidad sobre los enlaces no observados. [ 5 ]

Lógica blanda probabilística (PSL)

La lógica suave probabilística (PSL) es un modelo gráfico probabilístico sobre un campo aleatorio de Markov con pérdida de bisagra (HL-MRF). Los HL-MRF se crean mediante un conjunto de reglas de lógica de primer orden con plantillas, que luego se aplican a los datos. La PSL puede combinar información de atributos o local con información topológica o relacional. Si bien la PSL puede incorporar predictores locales, como la similitud del coseno , también admite reglas relacionales, como la compleción de triángulos en una red. [ 14 ]

Redes lógicas de Markov (RLM)

Las redes lógicas de Markov (MLN) son un modelo gráfico probabilístico definido sobre redes de Markov. Estas redes se definen mediante reglas de lógica de primer orden con plantillas, que luego se fundamentan en los datos de entrenamiento. Las MLN pueden incorporar reglas tanto locales como relacionales para la predicción de enlaces. [ 15 ]

Modelo R (RML)

R-Models (RMLs) es un modelo de red neuronal creado para proporcionar un enfoque de aprendizaje profundo al problema de predicción de pesos de enlaces. Este modelo utiliza una técnica de incrustación de nodos que extrae incrustaciones de nodos (conocimiento de los nodos) a partir de los pesos de los enlaces conocidos (relaciones entre nodos) y utiliza este conocimiento para predecir los pesos de los enlaces desconocidos. [ 16 ]

Aplicaciones

La predicción de enlaces ha encontrado diversos usos, pero cualquier dominio en el que las entidades interactúen de forma estructurada puede beneficiarse de ella. [ 17 ] Una aplicación común de la predicción de enlaces es la mejora de las medidas de similitud para los enfoques de filtrado colaborativo en la recomendación. La predicción de enlaces también se utiliza con frecuencia en redes sociales para sugerir amigos a los usuarios. Asimismo, se ha utilizado para predecir asociaciones delictivas.

En biología, la predicción de enlaces se ha utilizado para predecir interacciones entre proteínas en redes de interacción proteína-proteína. [ 18 ] La predicción de enlaces también se ha utilizado para inferir interacciones entre fármacos y objetivos mediante la predicción de enlaces. [ 19 ] Otra aplicación se encuentra en la predicción de colaboración en redes de coautoría científica.

La resolución de entidades , también conocida como deduplicación, utiliza comúnmente la predicción de enlaces para determinar si dos entidades en una red son referencias a la misma entidad física. Algunos autores han utilizado información contextual en dominios estructurados en red para mejorar la resolución de entidades. [ 20 ]

Véase también

Referencias

  1. ↑ Hasan, Mohammad Al; Zaki, Mohammed J. (2011). "Un estudio sobre la predicción de enlaces en redes sociales" (PDF) . En Aggarwal, Charu C. (ed.). Análisis de datos de redes sociales . Springer. pp. 243–275 . doi : 10.1007/978-1-4419-8462-3_9 . ISBN  978-1-4419-8461-6.
  2. ↑ Liben-Nowell, David; Kleinberg, Jon (2007). "El problema de la predicción de enlaces para redes sociales". Journal of the American Society for Information Science and Technology . 58 (7): 1019– 1031. CiteSeerX 10.1.1.58.689 . doi : 10.1002/asi.20591 . 
  3. ↑ Popescul, Alexandrin; Ungar, Lyle (2002). "Aprendizaje relacional estadístico para la predicción de enlaces" (PDF) . Taller sobre aprendizaje de modelos estadísticos a partir de datos relacionales .
  4. ↑ O'Madadhain, Joshua; Hutchins, Jon; Smyth, Padhraic (2005). "Algoritmos de predicción y clasificación para datos de redes basados ​​en eventos" (PDF) . Revista de la Sociedad Estadounidense de Ciencia y Tecnología de la Información .
  5. 1 2 Getoor, Lise; Friedman, Nir; Koller, Daphne; Taskar, Benjamin (2002). "Aprendizaje de modelos probabilísticos de la estructura de enlaces" . J. Mach. Learn. Res . 3 : 679–707 .
  6. ↑ Backstrom, Lars; Leskovec, Jure (2011). "Supervised random walks: predicting and recommending links in social networks". En King, Irwin; Nejdl, Wolfgang; Li, Hang (eds.). Proceedings of the Fourth International Conference on Web Search and Web Data Mining, WSDM 2011, Hong Kong, China, February 9-12, 2011 . ACM. pp. 635– 644. arXiv : 1011.4071 . doi : 10.1145/1935826.1935914 . 
  7. ↑ Menon, Aditya; Elkan, Charles (2011). "Predicción de enlaces mediante factorización matricial" (PDF) . Aprendizaje automático y descubrimiento de conocimiento en bases de datos . Notas de clase en informática. Vol. 6912. págs. 437–452 . doi : 10.1007/978-3-642-23783-6_28 . ISBN   978-3-642-23782-9. S2CID 13892350 . 
  8. 1 2 Xiao, Han; Huang, Minlie; Zhu, Xiaoyan (9 de julio de 2016). "De un punto a una variedad: incrustación de grafos de conocimiento para la predicción precisa de enlaces" . Actas de la Vigésimo Quinta Conferencia Internacional Conjunta sobre Inteligencia Artificial : 1315–1321 . arXiv : 1512.04792 .
  9. ↑ Getoor, Lise; Diehl, Christopher P. (2005). "Minería de enlaces: una revisión". Boletín informativo de ACM SIGKDD Explorations . 7 (2): 3– 12. doi : 10.1145/1117454.1117456 .
  10. ↑ Yu, Philip S.; Han, Jiawei; Faloutsos, Christos (2010). Link Mining: Models, Algorithms, and Applications . Springer. doi : 10.1007/978-1-4419-6515-8 . ISBN 978-1-4419-6514-1.
  11. ↑ Aggarwal, Charu (2015). Minería de datos . Springer. pp. 665–670 . 
  12. ↑ Adamic, Luda; Adar, Etyan (2003). "Amigos y vecinos en la web". Redes sociales . 25 (3): 211– 230. doi : 10.1016/S0378-8733(03)00009-1 . S2CID 2262951 . 
  13. ↑ Katz, L. (1953). "Un nuevo índice de estatus derivado del análisis sociométrico". Psychometrika . 18 : 39–43 . doi : 10.1007/BF02289026 . S2CID 121768822 . 
  14. ↑ Bach, Stephen; Broecheler, Matthias; Huang, Bert; Getoor, Lise (2017). "Campos aleatorios de Markov con pérdida de bisagra y lógica suave probabilística". Journal of Machine Learning Research . 18 : 1–67 . arXiv : 1505.04406 .
  15. ↑ Richardson, Matthew; Domingos, Pedro M. (2006). "Redes lógicas de Markov". Machine Learning . 62 ( 1– 2): 107– 136. doi : 10.1007/S10994-006-5833-1 .
  16. ↑ Hou, Yuchen; Holder, Lawrence B. (2019). "Sobre la minería de grafos con aprendizaje profundo: introducción del modelo R para la predicción del peso de los enlaces" (PDF) . J. Artif. Intell. Soft Comput. Res . 9 (1): 21– 40. doi : 10.2478/JAISCR-2018-0022 .
  17. ↑ Martínez, Víctor (2016). "Una revisión de la predicción de enlaces en redes complejas". ACM Computing Surveys . 49 (4): 1– 33. doi : 10.1145/3012704 . S2CID 14193467 . 
  18. ↑ Qi, Yanjun (2006). "Evaluación de diferentes datos biológicos y métodos de clasificación computacional para su uso en la predicción de interacciones proteicas" . Proteins : Structure, Function, and Bioinformatics . 63 (3): 490– 500. doi : 10.1002/prot.20865 . PMC 3250929. PMID 16450363 .  
  19. ↑ Shridar, Dhanya; Fakhraei, Shobeir; Getoor, Lise (2016). "Un enfoque probabilístico para la predicción de interacciones farmacológicas basadas en la similitud colectiva" (PDF) . Bioinformatics . 32 (20): 3175– 3182. doi : 10.1093/bioinformatics/btw342 . PMID 27354693 . 
  20. ↑ Bhattacharya, Indrajit; Getoor, Lise (2007). "Resolución colectiva de entidades en datos relacionales". ACM Transactions on Knowledge Discovery from Data . 1 : 5. doi : 10.1145/1217299.1217304 . hdl : 1903/4241 . S2CID 488972 .