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. Los 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 el momento, el objetivo es predecir los enlaces en el momento . La predicción de enlaces es de amplia aplicación. En el comercio electrónico, la predicción de enlaces suele ser una subtarea para recomendar elementos a los usuarios. En la conservación de bases de datos de citas, se puede utilizar para la deduplicación de registros. 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
Considere una red , dónde representa los nodos de la entidad en la red y X representa el conjunto de enlaces "verdaderos" entre entidades de la red. Se nos da el conjunto de entidadesy 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 enlaces verdaderos a la vez., y el objetivo es inferir el conjunto de vínculos verdaderos en el momento Por lo general, también se nos da un subconjunto de enlaces no observados llamados enlaces potenciales. , y necesitamos identificar vínculos verdaderos 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. Enfoques de predicción de enlaces para esta configuración aprende un clasificador que mapea enlaces en a etiquetas positivas y negativas, es decir . En la formulación de estimación de probabilidad, los vínculos potenciales se asocian con probabilidades de existencia. Enfoques de predicción de enlaces para esta configuración aprender un modelo que mapea enlaces en a una probabilidad, es decir .
Los enfoques de enlace único aprenden un modelo que clasifica cada enlace de forma independiente. Los enfoques de predicción estructurada capturan la correlación entre vínculos potenciales formulando la tarea como una tarea de predicción de vínculos colectivos. Los enfoques 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 se puede formular como una instancia de la tarea de estimación de valores perdidos. Aquí, el gráfico se representa como una matriz de adyacencia con valores perdidos. La tarea consiste en completar la matriz identificando los valores faltantes. Los métodos basados en la factorización matricial suelen utilizar esta formulación.
Historia
La tarea de la predicción de enlaces ha atraído la atención de varias comunidades de investigación que van desde estadísticas y ciencia de redes hasta aprendizaje automático y minería de datos . En estadística, los modelos de gráficos aleatorios generativos, como los modelos de bloques estocásticos, proponen un enfoque para generar vínculos entre nodos en un gráfico aleatorio . Para las redes sociales, Liben-Nowell y Kleinberg propusieron modelos de predicción de enlaces basados en diferentes medidas de proximidad de gráficos. [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. propuso un modelo de regresión logística estructurado que puede hacer uso de características relacionales. [3] Los modelos de probabilidad condicional local basados en atributos y características estructurales fueron propuestos por O'Madadhain et al. [4] Getoor ha propuesto varios modelos basados en modelos gráficos dirigidos para la predicción de enlaces colectivos. [5] Otros se acercaron en base a paseos aleatorios. [6] y la factorización de matrices también se han propuesto [7] Con la llegada del aprendizaje profundo, también se han propuesto varios enfoques basados en la incrustación de gráficos para la predicción de enlaces. [8] Para obtener más información sobre la predicción de enlaces, consulte la encuesta de Getoor et al. [9] y Yu et. Alabama. [10]
Enfoques y métodos
Se han propuesto varios enfoques de predicción de enlaces, incluidos los enfoques no supervisados, como las medidas de similitud calculadas en los atributos de la entidad, los enfoques basados en el recorrido aleatorio y la factorización matricial , y los enfoques supervisados basados en modelos gráficos y aprendizaje profundo . Los enfoques de predicción de enlaces se pueden dividir en dos categorías generales según el tipo de red subyacente: (1) enfoques de predicción de enlaces para redes homogéneas (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 topología
Los métodos basados en topología suponen, en términos generales, que es más probable que los nodos con una estructura de red similar formen un enlace.
Vecinos comunes
Este es un enfoque común para la predicción de enlaces que calcula el número de vecinos comunes . Es más probable que las entidades con más vecinos en común tengan un vínculo. Se calcula de la siguiente manera:
Una debilidad de este enfoque es que no tiene en cuenta el número relativo de vecinos comunes.
Medida Jaccard
La medida de Jaccard aborda el problema de los vecinos comunes calculando el número relativo de vecinos en común:
Medida adánica-Adar
La medida Adánica-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:
dónde es el conjunto de nodos adyacentes a.
Medida 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 gráficos dispersos. En estas situaciones, es apropiado utilizar métodos que tengan en cuenta las caminatas más largas. La medida de Katz [13] es una métrica que captura esto. Se calcula buscando en el gráfico trayectorias de longitud. en el gráfico y sumando los recuentos de cada longitud de ruta ponderados por pesos especificados por el usuario.
Sea A la matriz de adyacencia de una red en consideración. Elementosde A son variables que toman un valor 1 si un nodo i está conectado al nodo j y 0 en caso contrario. Los poderes de A indican la presencia (o ausencia) de enlaces entre dos nodos a través de intermediarios. Por ejemplo, en matrix, si elemento , indica que el nodo 2 y el nodo 12 están conectados a través de un paseo de longitud 3. Si denota la centralidad de Katz de un nodo i , luego matemáticamente:
Tenga en cuenta que la definición anterior utiliza el hecho de que el elemento en la ubicación de refleja el número total de grado de conexiones entre nodos y .
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 utilizados para medir la similitud. Las distancias pequeñas indican una mayor similitud.
Similitud de coseno
Después de normalizar los valores de los atributos, calcular el coseno entre los dos vectores es una buena medida de similitud, y los valores bajos indican una mayor similitud.
Métodos mixtos
Los métodos mixtos combinan métodos basados en atributos y topologías.
Incrustaciones de gráficos
Las incorporaciones de gráficos también ofrecen una forma conveniente de predecir enlaces. [8] Los algoritmos de incrustación de gráficos, como Node2vec , aprenden un espacio de incrustación en el que los nodos vecinos están representados por vectores para que las medidas de similitud de vectores, como la similitud del producto escalar o la distancia euclidiana, se mantengan en el espacio de incrustación. Estas similitudes son funciones tanto de características topológicas como de similitudes basadas en atributos. Luego, se pueden usar otras técnicas de aprendizaje automático para predecir bordes sobre la base de la similitud vectorial.
Modelos de relaciones probabilísticas
Un modelo relacional probabilístico (PRM) especifica una plantilla para una distribución de probabilidad en una base de datos. La plantilla describe el esquema relacional del dominio y las dependencias probabilísticas entre los atributos del dominio. Un PRM, 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 blanda probabilística (PSL) es un modelo gráfico probabilístico sobre el campo aleatorio de Markov con pérdida de bisagra (HL-MRF). Los HL-MRF se crean mediante un conjunto de reglas similares a la lógica de primer orden basadas en plantillas, que luego se basan en los datos. PSL puede combinar información local o de atributos con información topológica o relacional. Si bien PSL puede incorporar predictores locales, como la similitud de coseno , también admite reglas relacionales, como la finalización de triángulos en una red. [14]
Redes lógicas de Markov (MLN)
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 tipo lógico de primer orden basadas en plantillas, que luego se basan en los datos de entrenamiento. Los MLN pueden incorporar reglas tanto locales como relacionales con el propósito de predecir enlaces. [15]
Modelo R (RML)
R-Models (RML) es un modelo de red neuronal creado para proporcionar un enfoque de aprendizaje profundo al problema de predicción del peso del enlace. Este modelo utiliza una técnica de incrustación de nodos que extrae las incrustaciones de nodos (conocimiento de los nodos) de los pesos de los enlaces conocidos (relaciones entre los nodos) y utiliza este conocimiento para predecir los pesos de los enlaces desconocidos. [dieciséis]
Aplicaciones
La predicción de enlaces ha encontrado usos variados, pero cualquier dominio en el que las entidades interactúen de forma estructural puede beneficiarse de la predicción de enlaces. [17] Una aplicación común de la predicción de enlaces es mejorar las medidas de similitud para los enfoques de filtrado colaborativo para la recomendación. La predicción de enlaces también se utiliza con frecuencia en las redes sociales para sugerir amigos a los usuarios. También 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, comúnmente usa la predicción de enlaces para predecir si dos entidades en una red son referencias a la misma entidad física. Algunos autores han utilizado información de contexto en dominios estructurados en red para mejorar la resolución de entidades. [20]
La predicción de enlaces en el contexto de los efectos de red se ha utilizado para analizar las tendencias de propagación a través de las redes y se puede utilizar para mejorar las estrategias de marketing, en particular el marketing viral. [ cita requerida ]
Paquetes de software
Software gratuito y de código abierto
- Caffe
- CNTK
- Deeplearning4j
- DeepSpeed
- ELKI
- Infer.NET
- Keras
- Cuidador de elefantes
- Mazo
- ML.NET
- mlpack
- MXNet
- Laboratorio neuronal
- Octava
- OpenNN
- naranja
- Lenguaje de datos Perl
- Lógica blanda probabilística
- R
- RAÍZ (TMVA con RAÍZ)
- scikit-learn
- Shogun
- Spark MLlib
- SystemML
- TensorFlow
- Antorcha / PyTorch
- Weka / MOA
- Yooreeka
Software propietario con ediciones gratuitas y de código abierto
- KNIME
- RapidMiner
Software propietario
- Aprendizaje automático de Amazon
- Angoss KnowledgeSTUDIO
- Aprendizaje automático de Azure
- Ayasdi
- IBM Watson Studio
- API de predicción de Google
- IBM SPSS Modeler
- Modelador KXEN
- LIONsolver
- Mathematica
- MATLAB
- Microsoft Azure
- Diseñador neuronal
- NeuroSoluciones
- Minería de datos de Oracle
- Servicio en la nube de Oracle AI Platform
- RCASE
- SAS Enterprise Miner
- SecuenciaL
- Splunk
- Minero de datos STATISTICA
Ver también
- Similitud (ciencia de redes)
- Gráfico (matemáticas discretas)
- Modelo de bloque estocástico
- Lógica blanda probabilística
- Incrustación de gráficos
- Big data
- Aprendizaje basado en explicaciones
- Lista de conjuntos de datos para la investigación del aprendizaje automático
- Analítica predictiva
- Seq2seq
- Equidad (aprendizaje automático)
- Incrustaciones , para otros tipos de incrustaciones
- Espesor del libro
- Espesor del gráfico
- Lista de bordes doblemente conectados
- Mapa regular (teoría de grafos)
- Teorema de Fáry
- Node2vec
- Aprendizaje relacional estadístico
Referencias
- ^ Al Hasan, Mohammad; Zaki, Mohammed (2011). "Predicción de enlaces en redes sociales" (PDF) . Cite journal requiere
|journal=
( ayuda ) - ^ Liben-Nowell, David; Kleinberg, Jon (2007). "El problema de la predicción de enlaces para las redes sociales". Revista de la Sociedad Estadounidense de Ciencia y Tecnología de la Información . 58 (7): 1019–1031. doi : 10.1002 / asi.20591 .
- ^ Popescul, Alexandrin; Ungar, Lyle (2002). "Aprendizaje relacional estadístico para la predicción de enlaces" (PDF) . Taller de aprendizaje de modelos estadísticos a partir de datos relacionales .
- ^ O'Madadhain, Joshua; Hutchins, Jon; Smyth, Padhraic (2005). "Algoritmos de predicción y clasificación para datos de red basados en eventos" (PDF) . Revista de la Sociedad Estadounidense de Ciencia y Tecnología de la Información .
- ^ a b Getoor, Lise; Friedman, Nir; Koller, Daphne; Taskar, Benjamin (2002). "Aprendizaje de modelos probabilísticos de estructura de enlaces" (PDF) . Cite journal requiere
|journal=
( ayuda ) - ^ Backstrom, Lars; Leskovec, Jure (2011). "Caminatas aleatorias supervisadas: prediciendo y recomendando enlaces en redes sociales". doi : 10.1145 / 1935826.1935914 . S2CID 7851677 . Cite journal requiere
|journal=
( ayuda ) - ^ 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 . Apuntes de conferencias en Ciencias de la Computación. 6912 . págs. 437–452. doi : 10.1007 / 978-3-642-23783-6_28 . ISBN 978-3-642-23782-9.
- ^ a b Xiao, Han; al., et. (2015). "De un punto a un múltiple: incrustación de gráficos de conocimiento para una predicción de enlaces precisa". SIGMOD . arXiv : 1512.04792 .
- ^ Getoor, Lise; Diehl, Christopher (2005). "Minería de enlaces: una encuesta". doi : 10.1145 / 1117454.1117456 . S2CID 9131786 . Cite journal requiere
|journal=
( ayuda ) - ^ Yu, Philips; Han, Jiawei; Faloutsos, Christos (2010). "Minería de enlaces: modelos, algoritmos y aplicaciones". Cite journal requiere
|journal=
( ayuda ) - ^ Aggarwal, Charu (2015). Minería de datos . Saltador. págs. 665–670.
- ^ 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 .
- ^ Katz, L. (1953). "Un nuevo índice de estado derivado del análisis sociométrico". Psychometrika . 18 : 39–43. doi : 10.1007 / BF02289026 . S2CID 121768822 .
- ^ Bach, Stephen; Broecheler, Matthias; Huang, Bert; Getoor, Lise (2017). "Campos aleatorios de Markov de pérdida de bisagra y lógica blanda probabilística". Revista de investigación sobre aprendizaje automático . 18 : 1-67. arXiv : 1505.04406 .
- ^ Dominogs, Pedro; Richardson, Matthew (2006). "Redes lógicas de Markov" (PDF) . Cite journal requiere
|journal=
( ayuda ) - ^ Hou, Yuchen; Lawrence, Holder (2017). "PRESENTAMOS EL MODELO R PARA LA PREDICCIÓN DEL PESO DE LINK" (PDF) . Cite journal requiere
|journal=
( ayuda ) - ^ Martínez, Víctor (2016). "Una encuesta de predicción de enlaces en redes complejas". Encuestas de computación ACM . 49 (4): 1–33. doi : 10.1145 / 3012704 . S2CID 14193467 .
- ^ 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 de proteínas" . Proteínas: estructura, función y bioinformática . 63 (3): 490–500. doi : 10.1002 / prot.20865 . PMC 3250929 . PMID 16450363 .
- ^ Shridar, Dhanya; Fakhraei, Shobeir; Getoor, Lise (2016). "Un enfoque probabilístico para la predicción de la interacción fármaco-fármaco basada en la similitud colectiva" (PDF) . Bioinformática . 32 (20): 3175–3182. doi : 10.1093 / bioinformatics / btw342 . PMID 27354693 .
- ^ Bhattacharya, Indrajit; Getoor, Lise (2007). "Resolución de entidades colectivas en datos relacionales". Transacciones de ACM sobre descubrimiento de conocimientos a partir de datos (TKDD) . 1 : 5. doi : 10.1145 / 1217299.1217304 . hdl : 1903/4241 . S2CID 488972 .