En primer lugar, no te recomiendo el libro Social Network Analysis for Startups por Maksim Tsvetovat y Alexander Kouznetsov. Un libro como este es un regalo del cielo para los programadores que necesitan adquirir rápidamente una fluidez básica en una disciplina específica (en este caso, la teoría de grafos) para que puedan comenzar a escribir código para resolver problemas en este dominio. Ambos autores son teóricos de gráficos académicamente entrenados, pero la audiencia prevista de su libro son los programadores. Casi todos los numerosos ejemplos presentados en el libro están en python usando la biblioteca networkx.
En segundo lugar, para los proyectos que tiene en mente, dos tipos de bibliotecas son muy útiles si no es indispensable:
gráfico de análisis: por ejemplo, la excelente networkx (Python), o igraph (python, R, y otros.) son dos que puedo recomendar altamente; y
gráfico de representación: la excelente graphViz, que puede ser utilizado independiente desde la línea de comandos, pero es más probable que va a querer utilizarlo como una biblioteca; existen fijaciones Graphviz en los principales idiomas (por ejemplo, para el pitón hay por lo menos tres yo sepa, aunque pygraphviz es mi preferencia; para R no es rgraphviz que es parte de la suite bioconductor paquete). Rgraphviz tiene una excelente documentación (consulte en particular la viñeta incluida con el paquete).
Es muy fácil de instalar y comenzar a experimentar con estas bibliotecas, y en particular su uso
para aprender el gráfico léxico teórico esencial y unidades de análisis (por ejemplo, distribución de la secuencia grado, atravesamiento de nodos, operadores de gráfico );
para distinguir nodos críticos en un gráfico (por ejemplo, centralidad de grados, centralidad de vectores propios, surtido); y
para identificar prototipos de subestructuras de gráfico (por ejemplo, estructura bipartita, triángulos, ciclos, clicas, clústeres, comunidades y núcleos).
El valor de la utilización de una biblioteca gráfica-análisis para entender rápidamente estos elementos esenciales de la teoría de grafos es que en su mayor parte hay una 1: mapeo de 1 entre las conceptos i acabo de mencionar y funciones en la biblioteca (networkx o igraph).
Así, por ejemplo, puede generar rápidamente dos gráficos aleatorios de igual tamaño (número de nodo), renderizarlos y luego visualizarlos, luego calcular fácilmente por ejemplo la secuencia de grados promedio o la centralidad de intermediación para ambos y observar de primera mano cómo cambian el valor de esos parámetros afecta la estructura de un gráfico.
W/r/t la combinación de técnicas de ML y Graph Theoretic, aquí está mi experiencia personal limitada. Utilizo ML en mi trabajo cotidiano y en la teoría de grafos con menos frecuencia, pero rara vez en conjunto. Esta es solo una observación empírica limitada a mi experiencia personal, por lo que el hecho de que no haya encontrado un problema en el que parezca natural combinar técnicas en estos dos dominios. La mayoría de las veces, el análisis teórico de gráficos es útil en el punto ciego de ML, que es la disponibilidad de una cantidad sustancial de datos de entrenamiento etiquetados - las técnicas supervisadas de ML dependen en gran medida de esto.
Una clase de problemas para ilustrar este punto es detección/predicción de fraude en línea. Casi nunca es posible recopilar datos (por ejemplo, conjuntos de transacciones en línea atribuidas a un usuario en particular) que pueda separar con certeza razonable y etiquetar como "cuenta fraudulenta". Si fueran especialmente inteligentes y efectivos, se etiquetarían erróneamente como "legítimos" y para las cuentas para las cuales se sospechaba fraude, con bastante frecuencia los diagnósticos de primer nivel (p., verificación de id. adicional o un período de espera mayor para retirar dinero en efectivo) a menudo son suficientes para que cesen su actividad (lo que permitiría una clasificación definitiva). Finalmente, incluso si de alguna manera logras reunir un conjunto de datos razonablemente libre de ruido para entrenar tu algoritmo ML, ciertamente será un desequilibrio serio (es decir, mucho más "legítimo" que puntos de datos "fraudulentos"); este problema se puede gestionar con el preprocesamiento de las estadísticas (remuestreo) y con el ajuste del algoritmo (ponderación), pero sigue siendo un problema que probablemente degradará la calidad de los resultados.
Así que, aunque nunca he podido utilizar con éxito las técnicas ML para este tipo de problemas, en al menos dos casos, he utilizado la teoría de gráficos con cierto éxito - en la instancia más reciente, aplicando un modelo adaptado de el proyecto de un grupo en Carnegie Mellon inicialmente dirigido a detection of online auction fraud on ebay.
Solo para agregar a su gran libro de recomendación. Los autores (profesores de Stanford) tienen una clase gratuita a partir de este año: http://www.pgm-class.org/ – Lostsoul