El Fin Del Conocimiento - Bóveda 6/12 - CVPR - 2016 - Minería de Grandes Grafos: Patrones, Anomalías y Detección de Fraude

graph LR classDef main fill:#f9d4d4, font-weight:bold, font-size:14px classDef intro fill:#d4f9d4, font-weight:bold, font-size:14px classDef patterns fill:#d4d4f9, font-weight:bold, font-size:14px classDef methods fill:#f9f9d4, font-weight:bold, font-size:14px classDef applications fill:#f9d4f9, font-weight:bold, font-size:14px classDef future fill:#d4f9f9, font-weight:bold, font-size:14px Main["Minería de Grandes Grafos:
Patrones, Anomalías y
Detección de Fraude"] Main --> A["Introducción a la Minería de Grafos"] A --> A1["Faloutsos: minería de datos, grafos,
investigador de redes 1"] A --> A2["Grafos prevalentes en varios dominios 2"] A --> A3["Patrones y anomalías interrelacionados
en grafos 3"] A --> A4["Grafos reales exhiben patrones
no aleatorios 4"] A --> A5["Grado promedio menor que
grado máximo 5"] A --> A6["Distribuciones sesgadas impactan recursos
computacionales 6"] Main --> B["Patrones y Propiedades de Grafos"] B --> B1["Los valores propios siguen una
distribución de ley de potencias 7"] B --> B2["Participación en triángulos crece con
el grado del nodo 8"] B --> B3["Valores propios aproximan el conteo
total de triángulos 9"] B --> B4["Grafos reales siguen patrones de
ley de potencias 13"] B --> B5["Conciencia de patrones permite
cálculos rápidos 14"] B --> B6["Redes biológicas exhiben muchas
cliques 24"] Main --> C["Métodos y Técnicas"] C --> C1["Propagación de creencias descubre
fraude en redes 11"] C --> C2["Algoritmos de grafos relacionados con
ecuaciones matriciales 12"] C --> C3["Grafos que evolucionan en el tiempo
representados como tensores 16"] C --> C4["Descomposición de tensores descubre
componentes latentes 17"] C --> C5["Métodos escalables analizan grandes
tensores 19"] C --> C6["Análisis de tensores muestra actividad
coordinada 21"] Main --> D["Aplicaciones y Descubrimientos"] D --> D1["Minería de Twitter reveló nodos
sospechosos 10"] D --> D2["Descomposición reveló patrón de
llamadas inusual 18"] D --> D3["Big data revela patrones
ocultos previamente 20"] D --> D4["Métodos de tensores pueden detectar
fraude en seguros 25"] D --> D5["Aplicaciones del mundo real aprovechan
estas técnicas 28"] D --> D6["La minería de grafos impacta varias
aplicaciones 30"] Main --> E["Desafíos y Direcciones Futuras"] E --> E1["Detección de anomalías requiere herramientas
evolutivas 15"] E --> E2["Los defraudadores se adaptan a los
métodos de detección 22"] E --> E3["Distribuciones sesgadas desafían la
detección de anomalías 23"] E --> E4["Interdisciplinariedad clave para la
minería de grafos 26"] E --> E5["Comunidades superpuestas siguen siendo un desafío 27"] E --> E6["Problemas abiertos en la minería de grafos 29"] class Main main class A,A1,A2,A3,A4,A5,A6 intro class B,B1,B2,B3,B4,B5,B6 patterns class C,C1,C2,C3,C4,C5,C6 methods class D,D1,D2,D3,D4,D5,D6 applications class E,E1,E2,E3,E4,E5,E6 future

Resumen:

1.- La investigación de Christos Faloutsos se centra en la minería de datos y bases de datos, incluyendo la minería de grandes grafos, flujos, redes, fractales y bases de datos multimedia.

2.- Los grafos son prevalentes en muchos dominios, incluidos la web, redes sociales, redes informáticas, redes alimentarias, redes de blogs, seguridad informática y sistemas de recomendación.

3.- Los patrones y anomalías en los grafos van de la mano: notar un patrón te permite identificar puntos que no lo siguen como anomalías.

4.- Los grafos del mundo real no son aleatorios y exhiben muchos patrones, como distribuciones de grado de ley de potencias, distribuciones sesgadas de valores propios y muchos triángulos.

5.- El grado promedio es a menudo mucho menor que el grado máximo en grafos reales, a diferencia de lo que sugeriría una distribución gaussiana.

6.- No tener en cuenta las distribuciones de grado sesgadas puede llevar a una subestimación drástica de los recursos computacionales necesarios, por ejemplo, para cálculos de amigo de amigo.

7.- Los valores propios de grafos reales también siguen una distribución de ley de potencias, con los pocos valores propios principales siendo mucho más grandes que el resto.

8.- En las redes sociales, el número de triángulos en los que participa un nodo crece como la potencia 1.5 del grado del nodo.

9.- La distribución sesgada de valores propios puede aprovecharse para aproximar rápidamente el número total de triángulos en un grafo con un 99% de precisión.

10.- La minería de Twitter reveló nodos sospechosos con bajo grado pero participando en un número inusualmente alto de triángulos, que eran anunciantes adultos.

11.- La propagación de creencias y el diseño cuidadoso de matrices de compatibilidad pueden descubrir fraudes en grafos como la red de compradores-vendedores de eBay.

12.- La propagación de creencias rápida, los paseos aleatorios con reinicios y el aprendizaje semi-supervisado en grafos están todos relacionados mediante ecuaciones matriciales similares.

13.- Hay muchos patrones en grafos del mundo real, y la mayoría siguen leyes de potencias. Ignorar esto arriesga caer en la "trampa gaussiana".

14.- Notar patrones te permite hacer cálculos muy rápidos. Ignorarlos puede requerir petabytes de almacenamiento para operaciones básicas.

15.- La detección de anomalías nunca tendrá una respuesta final y requiere una lista creciente de herramientas. Los patrones y anomalías van de la mano.

16.- Los grafos que evolucionan en el tiempo pueden representarse como tensores, con llamante-receptor, autor-palabra clave-fecha o sujeto-verbo-objeto como modos típicos.

17.- La descomposición de tensores es un análogo de la SVD de matrices y puede descubrir componentes latentes significativos en tensores de múltiples modos.

18.- La descomposición de tensores de una red de quién-llama-a-quién a lo largo del tiempo descubrió un patrón inusual de "padrino llamando a subordinados".

19.- Métodos escalables de descomposición de tensores como GigaTensor y HAT-10-2 permiten el análisis de tensores muy grandes en Hadoop.

20.- Los big data ayudan a encontrar patrones que se perderían en muestras pequeñas, como pequeños grupos de anunciantes adultos en Twitter.

21.- El análisis de tensores de grafos que evolucionan en el tiempo puede revelar patrones sutiles como actividad periódica coordinada entre un pequeño grupo de nodos.

22.- Los defraudadores y la detección de anomalías están involucrados en una carrera armamentista: una detección más inteligente obliga a los defraudadores a adoptar estrategias más sofisticadas.

23.- Las distribuciones de valores sesgadas, como las leyes de potencias para montos de transacciones, hacen que los argumentos probabilísticos para la detección de anomalías sean más desafiantes.

24.- Las redes biológicas exhiben muchas cliques debido a, por ejemplo, grupos de proteínas que participan conjuntamente en una cadena de reacciones.

25.- El fraude en seguros puede manifestarse como cliques de médicos/farmacéuticos corruptos presentando reclamaciones falsas para pacientes ancianos. Los métodos de tensores pueden detectar esto.

26.- La interdisciplinariedad, combinando experiencia en el dominio, algoritmos y sistemas, es clave para extraer patrones y anomalías sutiles de grandes datos de grafos.

27.- Las comunidades superpuestas y los patrones fraudulentos sutiles siguen siendo un desafío y pueden requerir la inspección humana de los patrones detectados.

28.- Las aplicaciones del mundo real aprovechan estas técnicas, por ejemplo, Twitter y Facebook para la detección de fraudes, software policial para el análisis de delitos.

29.- Los problemas abiertos incluyen extender técnicas a grafos ponderados, abordar patrones superpuestos y probar la optimalidad teórica de detección de juegos.

30.- La minería de grafos y tensores potencia aplicaciones desde el fraude en línea hasta la investigación forense del crimen, destacando el amplio impacto potencial de estas técnicas.

Bóveda de Conocimiento construida porDavid Vivancos 2024