Незадача коммивояжера [i] жёлтый октябрь

Блокнот-компаньон (.ipynb) статьи на Хабре

Материал подготовил Вадим Сафронов в свободное от работы время на собственном оборудовании и данных, предоставленных г-жей Клинтон, для открытого курса машинного обучения сообщества Open Data Science. Распространяется на условиях лицензии Creative Commons CC BY-NC-SA 4.0. Можно использовать в любых целях (редактировать, поправлять и брать за основу), кроме коммерческих, но с обязательным упоминанием автора.

Лиссабон, 13 февраля 2018


План действий такой:

  1. Подготовка среды исполнения
  2. Загрузка данных
  3. Подход №1: кто кому пишет
  4. Подход №2: кого с кем ставят в копию
  5. Подход №3: кто кому пишет добрые письма
  6. Анализ структуры полученных сетей
  7. Метрики центральности
  8. Кластеризация
  9. Метод Маринки Житник
  10. Выводы и что-то вроде домашки

Подготовка среды исполнения

Вам потребуется 64-битная версия Python 2.7 и несколько дополнительных библиотек.

Все, кроме SNAP, ставится через pip.

Инструкция по установке SNAP: http://snap.stanford.edu/snappy/index.html

In [1]:
# импортируем необходимые библиотеки
import pandas as pd
import numpy as np

import snap

from sklearn.manifold import TSNE
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import KMeans

import urllib
import json

import matplotlib.pyplot as plt
%matplotlib inline

Данные

Та самая переписка, любезно предоставленная г-жей Клинтон, доступна после регистрации на сайте Kaggle по адресу: https://www.kaggle.com/kaggle/hillary-clinton-emails

Архив содержит готовую к использованию базу Sqlite и дублирует данные в нескольких файлах csv.

In [2]:
df = pd.read_csv('D:/!ClintonEmails/Emails.csv')
# для удобства будем использовать идентификатор документа в качестве индекса
df.index = df['Id']
# заглянем в ту самую переписку
df.head()
Out[2]:
Id DocNumber MetadataSubject MetadataTo MetadataFrom SenderPersonId MetadataDateSent MetadataDateReleased MetadataPdfLink MetadataCaseNumber ... ExtractedTo ExtractedFrom ExtractedCc ExtractedDateSent ExtractedCaseNumber ExtractedDocNumber ExtractedDateReleased ExtractedReleaseInPartOrFull ExtractedBodyText RawText
Id
1 1 C05739545 WOW H Sullivan, Jacob J 87.0 2012-09-12T04:00:00+00:00 2015-05-22T04:00:00+00:00 DOCUMENTS/HRC_Email_1_296/HRCH2/DOC_0C05739545... F-2015-04841 ... NaN Sullivan, Jacob J <Sullivan11@state.gov> NaN Wednesday, September 12, 2012 10:16 AM F-2015-04841 C05739545 05/13/2015 RELEASE IN FULL NaN UNCLASSIFIED\nU.S. Department of State\nCase N...
2 2 C05739546 H: LATEST: HOW SYRIA IS AIDING QADDAFI AND MOR... H NaN NaN 2011-03-03T05:00:00+00:00 2015-05-22T04:00:00+00:00 DOCUMENTS/HRC_Email_1_296/HRCH1/DOC_0C05739546... F-2015-04841 ... NaN NaN NaN NaN F-2015-04841 C05739546 05/13/2015 RELEASE IN PART B6\nThursday, March 3, 2011 9:45 PM\nH: Latest... UNCLASSIFIED\nU.S. Department of State\nCase N...
3 3 C05739547 CHRIS STEVENS ;H Mills, Cheryl D 32.0 2012-09-12T04:00:00+00:00 2015-05-22T04:00:00+00:00 DOCUMENTS/HRC_Email_1_296/HRCH2/DOC_0C05739547... F-2015-04841 ... B6 Mills, Cheryl D <MillsCD@state.gov> Abedin, Huma Wednesday, September 12, 2012 11:52 AM F-2015-04841 C05739547 05/14/2015 RELEASE IN PART Thx UNCLASSIFIED\nU.S. Department of State\nCase N...
4 4 C05739550 CAIRO CONDEMNATION - FINAL H Mills, Cheryl D 32.0 2012-09-12T04:00:00+00:00 2015-05-22T04:00:00+00:00 DOCUMENTS/HRC_Email_1_296/HRCH2/DOC_0C05739550... F-2015-04841 ... NaN Mills, Cheryl D <MillsCD@state.gov> Mitchell, Andrew B Wednesday, September 12,2012 12:44 PM F-2015-04841 C05739550 05/13/2015 RELEASE IN PART NaN UNCLASSIFIED\nU.S. Department of State\nCase N...
5 5 C05739554 H: LATEST: HOW SYRIA IS AIDING QADDAFI AND MOR... Abedin, Huma H 80.0 2011-03-11T05:00:00+00:00 2015-05-22T04:00:00+00:00 DOCUMENTS/HRC_Email_1_296/HRCH1/DOC_0C05739554... F-2015-04841 ... NaN NaN NaN NaN F-2015-04841 C05739554 05/13/2015 RELEASE IN PART H <hrod17@clintonemail.com>\nFriday, March 11,... B6\nUNCLASSIFIED\nU.S. Department of State\nCa...

5 rows × 22 columns

Как это нетрудно видеть, порядка нет и в данных, одна и та же личность в письмах упоминается по-разному

In [3]:
# проверим разночтения
df.MetadataFrom[df['MetadataFrom'].str.contains('Clinton') == True].unique()
Out[3]:
array(['Clinton, Hillary Rodham', 'Hillary Rodham Clinton',
       'Clinton Hillary R', 'Clinton, Hillary R'], dtype=object)

По счастливой случайности, добрые анонимусы составили списки уникальных адресатов, загрузим их

In [4]:
dfA = pd.read_csv('D:/!ClintonEmails/Aliases.csv')
dfP = pd.read_csv('D:/!ClintonEmails/Persons.csv')
dfR = pd.read_csv('D:/!ClintonEmails/EmailReceivers.csv')
In [5]:
# заглянем, что там в списке
dfP.info()
<class 'pandas.core.frame.DataFrame'>
RangeIndex: 513 entries, 0 to 512
Data columns (total 2 columns):
Id      513 non-null int64
Name    513 non-null object
dtypes: int64(1), object(1)
memory usage: 8.1+ KB
In [6]:
# и посчитаем уникальные значения
dfP['Name'].nunique()
Out[6]:
513

Подход №1: кто кому пишет

Создадим направленный граф, в котором узлами будут участники переписки, а ребрами - сообщения

In [7]:
G1 = snap.TNGraph.New()
In [8]:
# каждому адресату присвоим узел в графе
for item in dfP['Id']:
    G1.AddNode(int(item))
In [9]:
# проверим, сколько их таких
G1.GetNodes()
Out[9]:
513
In [10]:
# создадим несколько вспомогательных словарей, позволяющих привязать имена к идентификаторам
Senders = df['SenderPersonId'].dropna().astype(int).to_dict()
Subjects = df['MetadataSubject'].dropna().to_dict()
Bodies = df['ExtractedBodyText'].dropna().to_dict()

Names = dfP['Name'].to_dict()

dfA.index = dfA['Alias']
Aliases = dfA['PersonId'].to_dict()
In [11]:
# пройдем по списку получателей и для каждого письма создадим ребро, соединяющее с отправителем
i = 0
for item in dfR.iterrows():
    try:
        G1.AddEdge(Senders[item[1][1]], int(item[1][2]))
    except:
        i += 1
print 'Missing sender count: ', i
Missing sender count:  33
In [12]:
# пересчитаем рёбра
G1.GetEdges()
Out[12]:
739

Подход №2: кого с кем ставят в копию

In [13]:
G2 = snap.TNGraph.New()
In [14]:
for item in dfP['Id']:
    G2.AddNode(int(item))
In [15]:
# данные всегда будут грязными, и 80% времени уходит их приведение в человеческий вид
unknownTo = 0
unknownCc = 0

# пройдемся по документам
for item in df[['MetadataTo', 'ExtractedCc']].dropna().iterrows():
    emailTo = ''
    emailCc = ''
    
    err1 = 0
    
    # попробуем идентифицировать получателя
    try:
        emailTo = Aliases[str.lower(item[1][0]).replace(',', '').strip()]
    except:
        err1 = 1
        unknownTo += 1
    
    # и список всех тех, кого поставили в копию
    try:
        # который разобьём на части
        emailCcBulk = str.lower(item[1][1]).strip().split(';')
#        print emailTo, emailCcBulk
        for jtem in emailCcBulk:
            err2 = 0
            # которые попробуем идентифицировать в списке, который подготовили добрые анонимусы
            try:
                emailCc = Aliases[jtem.strip()]
#                print (emailTo, emailCc)
            except:
                err2 = 1
                unknownCc += 1
        # если все попытки оказались успешны
        if err1 == 0 and err2 == 0:
            # добавим ребро
            G2.AddEdge(int(emailTo), int(emailCc))

    except:
        err2 = 1
In [16]:
# пересчитаем узлы и рёбра
G2.GetNodes(), G2.GetEdges()
Out[16]:
(513, 81)
In [54]:
# сколько тех неизвестных получателей
unknownTo
Out[54]:
9
In [17]:
# и тех, кого в копию ставили
unknownCc
Out[17]:
3907

Видимо, добрые анонимусы не сильно утруждались разбором адресатов и для качественного анализа хорошо бы продолжить чистку данных. Это увлекательное занятие мы предоставим тем, кому действительно интересно узнать, что же именно творилось в переписке и кого с кем в копию ставили, а сами же перейдем к следующему шагу.

Подход №3: кто кому пишет добрые письма

Плохие новости

Обратите внимание: использованный API имеет ограничение на 1000 вызовов в день для одного IP адреса, а писем - 7945.

Тем, кого действительно интересует детальный анализ эмоциональной окраски переписки, рекомендуют синтаксически идентичную альтернативу, позволяющую бесплатно анализировать 45000 запросов в месяц https://market.mashape.com/japerk/text-processing/pricing

In [18]:
G3 = snap.TNGraph.New()
In [19]:
for item in dfP['Id']:
    G3.AddNode(int(item))
In [20]:
%%time

i = 0
for item in dfR.iterrows():
    try:
        # отбросим слишком короткие сообщения
        if len(Bodies[item[1][1]]) > 10:
            
            print 'long enough!'
        
            # закодируем содержимое сообщения для передачи в строке URL
            data = urllib.urlencode({"text": Bodies[item[1][1]]}).encode('utf-8')
            # отправим в API
            f = urllib.urlopen("http://text-processing.com/api/sentiment/", data)
            # прочитаем ответ
            json_string = f.read()
            # конвертируем джейсона в словарь
            my_parsed_json = json.loads(json_string)
            # да и закроем дескриптор файла
            f.close()

            print my_parsed_json['label']
            
            # только позитив!
            if my_parsed_json['label'] == 'pos':
                # отражается в рёбрах
                G3.AddEdge(Senders[item[1][1]], int(item[1][2]))
                print (Senders[item[1][1]], int(item[1][2])), my_parsed_json['probability']['pos']

    except:
        i += 1
    
    # прервем цикл, чтобы не мучать API зазря - интернет не резиновый
    if i > 1000:
        break
print 'Dropped due to non-positive sentiment or too short message count: ', i
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
long enough!
Dropped due to non-positive sentiment or too short message count:  101
Wall time: 31.3 s
In [280]:
# на всякий случай оставлю здесь пример ответа API
my_parsed_json
Out[280]:
{u'label': u'pos',
 u'probability': {u'neg': 0.41762556577746013,
  u'neutral': 0.39314763871467634,
  u'pos': 0.5823744342225399}}

Анализ структуры полученных сетей

Проведем на примере первого из полученных графов:

In [227]:
# воспользуемся готовой функцией и сохраним статистики в файл
snap.PrintInfo(G1, "Who sends emails to whom", "D:/!ClintonEmails/output.txt", False)
# который прочитаем построчно, избавляясь походу от пробелов и символов перевода строки
map(lambda x: x.strip(), open("D:/!ClintonEmails/output.txt").readlines())
Out[227]:
['Who sends emails to whom: Directed',
 'Nodes:                    513',
 'Edges:                    739',
 'Zero Deg Nodes:           45',
 'Zero InDeg Nodes:         100',
 'Zero OutDeg Nodes:        388',
 'NonZero In-Out Deg Nodes: 70',
 'Unique directed edges:    739',
 'Unique undirected edges:  633',
 'Self Edges:               0',
 'BiDir Edges:              212',
 'Closed triangles:         291',
 'Open triangles:           58406',
 'Frac. of closed triads:   0.004958',
 'Connected component size: 0.863548',
 'Strong conn. comp. size:  0.134503',
 'Approx. full diameter:    4',
 '90% effective diameter:  2.777670']

Метрики центральности

Eigenvector Centrality

Оценивает, насколько узел связан с наиболее связанными узлами графа. Метрика позволяет выявить наиболее влиятельных стейкхолдеров.

(https://en.wikipedia.org/wiki/Eigenvector_centrality)

In [254]:
# создадим ненаправленную проекцию графа
G1u = snap.ConvertGraph(snap.PUNGraph, G1)
In [255]:
# удалим несвязанные узлы
snap.DelZeroDegNodes(G1u)
In [117]:
# создадим хеш-таблицу для хранения значений метрики каждого узла 
NIdEigenH = snap.TIntFltH()
# вычислим
snap.GetEigenVectorCentr(G1u, NIdEigenH)
# отсортируем
NIdEigenH.SortByDat(False)

j = 0
for item in NIdEigenH:
    # и заглянем в топ 10
    if j < 10:
        print Names[item], NIdEigenH[item]
        j += 1
    else:
        break
('Hillary Clinton', 0.6560955820162151)
('Huma Abedin', 0.1740863339044756)
('Cheryl Mills', 0.15694747535239584)
('Jake Sullivan', 0.14097713411708188)
('Judith McHale', 0.09270708783888638)
('Philippe Reines', 0.09051170241484548)
('Lona Valmoro', 0.08718508012318242)
('Richard Verma', 0.08096735110870792)
('Anne-Marie Slaughter', 0.07620439695744603)
('Lissa Muscatine', 0.07476052809815743)

Betweenness Centrality

Оценивает количество кратчайших путей, проходящих через узел. Метрика позволяет определить, через кого проходят потоки информации, например, и выявить, через кого из стейкхолдеров "договариваются" отделы.

(https://en.wikipedia.org/wiki/Betweenness_centrality)

Вот так толпа случайных бродяг демонстрирует принцип вычисления метрики:

In [122]:
# хеш-таблица для метрик узлов
Nodes = snap.TIntFltH()
# и рёбер
Edges = snap.TIntPrFltH()
# вычислим
snap.GetBetweennessCentr(G1, Nodes, Edges, 1.0)

# отсортируем
Nodes.SortByDat(False)
Edges.SortByDat(False)

k = 0
for node in Nodes:
    # кто там в топе?
    if k <10:
        print "node: %s centrality: %f" % (Names[node], Nodes[node])
        k += 1
    else:
        break
node: Hillary Clinton centrality: 85027.531777
node: Cheryl Mills centrality: 14877.377015
node: Huma Abedin centrality: 12163.774634
node: Jake Sullivan centrality: 5083.696062
node: Harold Hongju Koh centrality: 3066.000000
node: Judith McHale centrality: 2758.491392
node: Philippe Reines centrality: 1915.930586
node: Sidney Blumenthal centrality: 1758.333333
node: Lauren Jiloty centrality: 1574.775000
node: Betsy Ebeling centrality: 1324.925000

Данная метрика позволяет оценить не только узлы, но и ребра графа, и выявить самые важные связи.

In [129]:
for edge in Edges:
    if k <20:
        print "edge: (%s -> %s) centrality: %f" % (Names[edge.GetVal1()], Names[edge.GetVal2()], Edges[edge])
        k += 1
    else:
        break
edge: (Cheryl Mills -> Hillary Clinton) centrality: 18612.269048
edge: (Hillary Clinton -> Huma Abedin) centrality: 13835.738095
edge: (Harold Hongju Koh -> Hillary Clinton) centrality: 5881.600000
edge: (Hillary Clinton -> Jake Sullivan) centrality: 5176.269048
edge: (Hillary Clinton -> Judith McHale) centrality: 4043.925824
edge: (Hillary Clinton -> Sidney Blumenthal) centrality: 3523.000000
edge: (Cheryl Mills -> Huma Abedin) centrality: 2971.159524
edge: (Hillary Clinton -> Philippe Reines) centrality: 2879.690476
edge: (Betsy Ebeling -> Hillary Clinton) centrality: 2801.066667
edge: (Hillary Clinton -> Voda Ebeling) centrality: 2791.733333

Page Rank

Оценивает вероятность нахождения случайного бродяги, гуляющего по рёбрам между узлами. Метрика является одной из самых важных в алгоритме ранжирования результатов поиска Google.

(https://en.wikipedia.org/wiki/PageRank)

In [127]:
# хеш-таблица для значений метрики узлов
PRankH = snap.TIntFltH()
# вычислим
snap.GetPageRank(G1, PRankH)
# отсортируем
PRankH.SortByDat(False)

l = 0
for item in PRankH:
    # заглянем в топ
    if l < 10:
        print Names[item], PRankH[item]
        l += 1
    else:
        break
Hillary Clinton 0.109261567868
Huma Abedin 0.0100701960367
Jake Sullivan 0.00915925521601
Cheryl Mills 0.0075538696409
Philippe Reines 0.0040521311586
Jacob Lew 0.00405009146221
Barack Obama 0.00369152323493
Lissa Muscatine 0.00350400532307
Melanne Verveer 0.00324716462651
Lona Valmoro 0.00323850249077

Опа! В списке важных лиц появляется Барак Обама

Не зря PageRank так крут, ой, не зря.


Кластеризация

Метод Гирвана-Ньюмана

(https://en.wikipedia.org/wiki/Girvan%E2%80%93Newman_algorithm)

Подробнее о модулярности: https://en.wikipedia.org/wiki/Modularity_(networks)

In [267]:
# вектор целочисленных векторов, в который мы запишем полученные разбиением графа сообщества
CmtyV = snap.TCnComV()
# разобьём граф на части и вычислим модулярность
modularity = snap.CommunityGirvanNewman(G1u, CmtyV1)
m = 1
for Cmty in CmtyV:
    print "\n-----------------\nCommunity: %d\n-----------------" % m
    m += 1
    for NI in Cmty:
        print Names[NI]
        
print "\nThe modularity of the network is %f" % modularity
-----------------
Community: 1
-----------------
American Beverage Association
Anthony Lake
Ban Ki-moon
Barbara Mikulski
Brian Greenspun
Caroline Adler
Case Button
Cherie Blair
Christopher Butzgy
Christopher Hill
Colin Powell
Council on Foreign Relations
Craig Kelly
Dana Hyde
Daniel
Danielle Brian
David Axelrod
David Garten
David Miliband
Derek Chollet
Eric Woodard
Esther Brimmer
George Mitchell
Gina Glantz
Han Duk-soo
Hillary Clinton
Jackie Newmyer
James Smith
Jan Piercy
Joanne Laszczych
John Podesta
Johnnie Carson
Jonathan Prince
KellyC@state.gov
Kent Conrad
Lee Feinstein
Linda Dewan
Lisa Caputo
Lois Quam
Luis CdeBaca
Lynn Forester de Rothschild
M. Albright
Madeleine Albright
Max Baucus
Michele Flournoy
Miguel Rodriguez
Mike
Nancy Parrish
Neera Tanden
Nora Tov
Paul Jones
Piper Campbell
Recos
Reines Philippe
Reta Jo Lewis
Richard Holbrooke
Rick Sloan
Robert Blake
Robert Danford
Rodriguez Miguel
Samuel Berger
Scott Gration
Terry Duffy
Thomas Donilon
Thomas Shannon
Tina Flournoy
Zachary Iscol
alcb
l
mhcaleja@state.gov
postmaster@state.gov
rooneym@state.gov
russorv@stategov
su ii iva gll@state.gov.
sullivahu@state.gov
russoiv@state.gov
miliscd@stategov
abedinh@stategov
tanleyrnr@state.gov
hanleymr@stategov
rnillscd@state.gov
rnillscd@stategov.
reiriesp@state.gov
suilivanii@stategov
sullivanj@state.gov
suilivanij@state.gok
hanleymr@state.gov.
hanleyrnr@state.gov
hanleymrgastategov
sulliyanfostate.gott
aliilscd@state.gov
nidesth@stategoy
millscd@state.gov.
sullivanji@state.gov
sullivanjj@state.golt
millscd@state.goy
nulandyj@state.goy
sulliyanij@state.goy
rnillscd@state.govs
jilotylc@state.gov.
jake.sulliyan
michele.fl
cheryimills millscd@state.gov
jake.sulliva
habedin b6
cheryl.mills jake.sullivan
abedinh@state.gov.
millscd@state.aov
illotylc@state.gov
millscd@state ov
habedin(
sullivanij@state.gov.
preines@
abedinh  state ov
cheryl.mills abedinh@state.gov
briar
abedinh@state.goy
a bedinh@state.gov
valmorol.1@state.gov
sullivanij@state.gov
preines sullivanjj@state.gov b6
valmorolj@state.gov.
leltmanjd@state.gov
ullivanjj@state.gov
sta i bott
sullivanjj©state ov
millscd@state.00v.
steinbergib@state.gov
cheryl.millf.
mhcaleja@state.gove
cheryl.millsi
s abedinh@state.gov
chetyl.mills sullivanij@state.gov
sullivanu@state.gov.
muscatinel@state.goy
preines  sullivanjj@state.gov
axelrod_
wburns6
valmorol1@state.gov.
steinberg1b@state.gov
. huma abedin
abedinh@stategovl
reinesp@state.goy
sulliyanjj@state.goy
emillscd@state.gov
cheryl.mill sullivanjj@state.gov
cheryl.mills millscd@state.gov.
jilotylc@state.goy
val moro u@state.gov
a bed inh@state.gov
mot lc@state.gov
jilot lc@state. ov
.1ilotylc@state.gov.
iilotylc@state.gov.
jilotylc©state.gov.
cheryl.mills sullivanjj@state.gov
iewjj@state.gov
cheryl.mills _
sulliva njj@state.g ov
pverveel
preines sullivanij@state.gov.
sta ibott
balderstonkm@state.gov.
rossdb@state.gov
bowens
jacobjlev
yeryeerms@state.goy
preines b6
valmorou@state.gove
abedinh@state.gove
nancy millscd@state.gov b6
vanbuskirk michael 1
caputo
.gordonph@state.gov.
preines sullivanjj@state.gov
cheryl.mills sullivanjj@state.gov b6
cheryl.mills( sullivanjj@state.gov
huma abedin b6
mtorrey1
glantz.gina
millscd@tate.gov
cheryl.mills huma abedin
cheryl.mills millscd@state.gov
campbelikm©state.gov
jacobjlew vermarr@state.gov
sullivanjj@state.gov b6
iilotylc@state.gov
rnillscd@state.gov.
sullivanjj@state.govr
lewij@state.gov
williamsbarrett millscd@state.gov.
abedinh©state.gov
s sullivanjj@state.gov
filotylc@state.gov.
..lilotylc@state.gov.
baer.danie
millscd@state.ov
iewij@state.gov
ieltmanjd@state.gov.
todd stern
jonespw2@state.gov.
daniel.baer@
jonespw2@state.gov
sbwhoeop b6
esullivanjj@state.gov
cheryl.miils@ millscd@state.gov
eabedinh@state.gov
abedinh@state.govr
cheryl.mills@ millscd@state.gov.
lewjj@state.gov.
sbwhoeopi
rshal
millscd@state. ov
jacobjle iewjj@state.gov b6
steinberg1b@state.gov.
ogordonph@state.gov.
crowley @state.  ov
sbwhoeo
sullivanij@state.gove
p rei n es
imuscatine huma abedin b6
tillemannts@state.gov.
markjpenr
vaimorou@state.gov
prein6
sullivanjj@state.goy
. vermarr@state.gov
sullivanjj@siate.gov
.filotylc@state.gov.
bstrider mmoore
.1ilotylc@state.gov
abed inh@state.gov.
iynn
a bed in h@state.gov
jake.sullivar preines
capriciamarshall huma abedin
jilotylc©state.gov
marshallcp@state.goy
hanle mr@state.gov
ha nleym r@state.gov

-----------------
Community: 2
-----------------
Andrew Shapiro
Anne-Marie Slaughter
Arturo Valenzuela
Carlos Pascual
Courtney Beale
David Johnson
Diane Reynolds
Doug Hattaway
Ellen Tauscher
Jacob Lew
Jake Sullivan
James Steinberg
Jeffrey Farrow
Jeffrey Feltman
Judith McHale
Kurt Campbell
Lissa Muscatine
Maria Otero
Megan Rooney
Melanne Verveer
PVervee
Philip Crowley
Philip Gordon
Philippe Reines
Rajiv Shah
Richard Verma
Robert Hormats
Thomas Nides
Todd Stern
Tomicah Tillemann
Wendy Sherman
William Burns
aclb
nuiand victoria j
reines philippe f
sullivan jacob j nuland victoria 1
jacob j sullivan
jake.sullivar
preines huma abedin
cdm
pj
crowleyp  state ov. preines
marciel scot a
holbrooke richard c
daniel.bae
vanbuskirk michael .3
preine h
preines h
adams david s
doug hattaway
dimartino kitty
waxman sharon l
jai:e sullivan
hume abed in
ramamurthy
h i
evergreen
lona valmoro
fl
lew jacobi
preine5
jake.sullivan h
feldman daniel f
ruggiero frank 3
singh vikram
s_specialassistants

-----------------
Community: 3
-----------------
Cheryl Mills
Christopher Edwards
Claire Coleman
Daniel Baer
Doug Band
G. Lou de Bac
Janice Jacobs
Jim Kennedy
John Olver
Justin Cooper
LGraham
Lourdes Cue
Maggie Williams
Maura Pally
Michael Posner
Michele Bond
Nora Toiv
Oscar Flores
Phillip Crowley
Rene Preval
Samuel ("Sandy") Berger
Strobe Talbott
Suzanne Grantham
Victoria Nuland
b6
oscar flores
reines philippe t
doug band
cmills
otero mildred (clinton)
cmarshal
lew jacob i
steinberg james
williamsbarre0
capricia penavic marshall
maggie williams
jim kennedy
.
smith daniel b
il
cheryl.mill1
edwards christopher (jakarta/pro)
williamsbarret
sawsanhassan1
stanton katie
jcooper
lgraham doug band
berniertoth michelle
coley theodore r
pcharron

-----------------
Community: 4
-----------------
Burns Strider
Donald
Huma Abedin
Laurie Rubiner
Maria Calivis
Mark Hyman
Oscar Lores
Rosemarie Howe
Susan Rice
mh.interiors
rrh.interiors
sullivanjj@state.gov.
hanieymr@state.gov
valmoroll@state.gov.
valmorou@state.gov
filotylc@state.gov
valmorou@state.gov.
valmorou©state.gov
preines verveerms@state.gov
campbelikm@state.gov
valmorou©state.gov.
valmoroll@state.gov
rosemarie.howe h
justin cooper
rosemarie howe
sullivanii@state.govr
luzzatt
valmorou state. ov
sullivanii@state.gov
hannah richert
kritenbrink daniel j
irussorv@state.gov
valmorol1@state.gov
valmorou@state.goy
valmdrou@state.gov
sullivanii@state.gov.
hai
laurenjiloty jilotylc@state.gov
ian1evqr@state.gov
woodardew@state.gov
jon davidson

-----------------
Community: 5
-----------------
Betsy Ebeling
Bonnie Klehr
Capricia Marshall
Lona Valmoro
Luzzatto
Monica Hanley
Patrick Kennedy
Robert Russo
habedin
huma abed in
cheryl.mill abedin huma
hume abedin
jpier4
abdinh@state.gov
bonnie klehr

-----------------
Community: 6
-----------------
KPK
Lauren Jiloty
Voda Ebeling
h b6
valmoro lona .1
elaine weiss
kevin m. okeefe
michael m. conway
laurenjiloty
monica.hanle

-----------------
Community: 7
-----------------
Harold Hongju Koh
Jennifer Robinson
eichensehr kristen e
hooke kathleen h
johnson clifton m
tones susan
townley stephen g
torres susan

-----------------
Community: 8
-----------------
Sidney Blumenthal
cheryl.mill
millscd©state.gov
doua band
declan kelly
sid blumenthal

-----------------
Community: 9
-----------------
Daniel Schwerin
Joshua Daniel
Michael Fuchs
preine

-----------------
Community: 10
-----------------
Bill Clinton
Chelsea Clinton
Tsakina Elbegdori
dad mom

-----------------
Community: 11
-----------------
Kris Balderston
Mark Penn
Marty Torrey

-----------------
Community: 12
-----------------
Govenman Etazini
Haiti
United States of America

-----------------
Community: 13
-----------------
Barack Obama
Daniel Inonye
James McGovern

-----------------
Community: 14
-----------------
ASUNCION
STATE
WHADP

-----------------
Community: 15
-----------------
Peter Robinson
Prime Minister

-----------------
Community: 16
-----------------
New York Times
harris jennifer m

-----------------
Community: 17
-----------------
Karl Eikenberry
Lee Brown

-----------------
Community: 18
-----------------
Kabul LGF Request
Werner Ilic

-----------------
Community: 19
-----------------
Department of State
Long Term Strategy Group

-----------------
Community: 20
-----------------
Alec
Cheryl

The modularity of the network is 0.482324

Метод Маринки Житник

Из одного источника данных можно построить несколько графов, описывающих отношения между рассматриваемыми сущностями и анализировать их по-отдельности. Альтернативой является http://snap.stanford.edu/ohmnet/ - один из проектов группы анализа больших сетей в университете Стенфорда.

Подготовим входные данные для обработки методом, реализацию которого для Python можно скачать здесь: https://github.com/marinkaz/ohmnet

In [25]:
# сохраним списки рёбер
snap.SaveEdgeList(G1, 'C:\ohmnet-master\data\edgelists\G1.txt')
snap.SaveEdgeList(G2, 'C:\ohmnet-master\data\edgelists\G2.txt')
snap.SaveEdgeList(G3, 'C:\ohmnet-master\data\edgelists\G3.txt')
In [45]:
# обозначим иерархию отношений между графами - вот тут можно поиграться
hier = '''relations\tdata/edgelists/G1.txt'''
#relations\tdata/edgelists/G2.txt
#relations\tdata/edgelists/G3.txt'''

text_file = open('C:\ohmnet-master\data\hier.txt', "w")
text_file.write("%s" % hier)
text_file.close()

# список списков рёбер графов
graphs = '''data/edgelists/G1.txt'''
#data/edgelists/G2.txt
#data/edgelists/G3.txt'''

text_file = open('C:\ohmnet-master\data\input.txt', "w")
text_file.write("%s" % graphs)
text_file.close()

Следующий шаг нужно выполнить в командной строке в основной директории OhmNet

В моём случае это C:\ohmnet-master\

python main.py --input "data/input.txt" --outdir "tmp2" --hierarchy "data/hier.txt"

Разберём выходные данные OhmNet

In [46]:
# создадим заголовки для колонок полученного 128-мерного представления
cols = [['id'] + ['f' + str(x+1000)[-3:] for x in range(128)]]

dfO = pd.read_csv('C:/ohmnet-master/tmp2/internal_vectors.emb', skiprows=1, sep=' ', header=None)
# присвоим заголовки колонкам
dfO.columns = cols 
dfO.info()
<class 'pandas.core.frame.DataFrame'>
RangeIndex: 443 entries, 0 to 442
Columns: 129 entries, id to f127
dtypes: float64(128), object(1)
memory usage: 446.5+ KB
In [47]:
# очистим идентификаторы узлов от технической информации - заголовков узлов иерархии
dfO['id'] = dfO['id'].apply(lambda x: x.split('__')[1])
In [48]:
# полюбуемся данными
dfO.head()
Out[48]:
id f000 f001 f002 f003 f004 f005 f006 f007 f008 ... f118 f119 f120 f121 f122 f123 f124 f125 f126 f127
0 344 -0.068063 -0.070226 0.227094 0.090542 -0.165523 0.156343 0.116478 0.112691 -0.091977 ... 0.074132 0.029889 -0.054278 0.069385 0.041662 0.094653 -0.049506 -0.117164 -0.086153 -0.053500
1 345 -0.065403 -0.071409 0.219886 0.082726 -0.159938 0.143335 0.103030 0.108755 -0.086146 ... 0.077265 0.028314 -0.046454 0.071125 0.037454 0.089442 -0.042936 -0.115028 -0.084975 -0.057507
2 346 -0.065195 -0.060854 0.223105 0.092140 -0.155407 0.154485 0.107320 0.108852 -0.083847 ... 0.069581 0.025817 -0.049203 0.071180 0.037703 0.094353 -0.046584 -0.116803 -0.081034 -0.056611
3 347 -0.069536 -0.067001 0.219709 0.091831 -0.155389 0.153590 0.114032 0.109359 -0.090777 ... 0.073751 0.030587 -0.054185 0.071176 0.041761 0.093283 -0.042749 -0.110406 -0.085837 -0.058237
4 340 -0.068964 -0.068171 0.220054 0.090149 -0.163179 0.147357 0.109213 0.106191 -0.087687 ... 0.072001 0.029772 -0.049555 0.066261 0.039615 0.091235 -0.046614 -0.116452 -0.082781 -0.053181

5 rows × 129 columns

Заглянем в многомерное пространство с помощью алгоритма t-sne

In [49]:
%%time
X_scaled = dfO.drop(['id'], axis=1)
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X_scaled)

tsne = TSNE(random_state=42)
tsne_representation = tsne.fit_transform(X_scaled)
Wall time: 16.9 s
In [50]:
plt.scatter(tsne_representation[:, 0], tsne_representation[:, 1]);

И проведем кластеризацию методом К-средних

In [53]:
inertia = []
for k in range(1, 20):
    kmeans = KMeans(n_clusters=k, random_state=42).fit(X_scaled)
    inertia.append(np.sqrt(kmeans.inertia_))

plt.plot(range(1, 20), inertia, marker='s');
plt.xlabel('$k$')
plt.ylabel('$J(C_k)$');

Бремя выводов

Как известно, штука нелегкая.

Мы заглянули в ту самую переписку, о которой гудели все, кому не лень и показали, что из одного источника данных можно построить множество графов, ограниченное только фантазией и размером оперативной памяти. Благодаря компактному представлению данных в библиотеке SNAP у нас есть возможность обрабатывать больше графов и быстрее. Также мы показали пример применения классических методов сетевого анализа, а их в SNAP немало, подробнее можно узнать из официального руководства по адресу https://snap.stanford.edu/snappy/doc/reference/index-ref.html.

Задача разбиения стейкхолдеров на группы - важная часть деятельности руководителя проектов, от которой часто болит голова. Какой способ лучше - вопрос открытый, да и область развивается. Как мы видим из примера применения одного из первых алгоритмов, метода Гирвана-Ньюмана, из одной только структуры потоков сообщений мы можем выделить интерпретируемые группы, вроде семейства Клинтон (Community: 10 - Bill Clinton, Chelsea Clinton, Tsakina Elbegdori, dad mom). Расскажите любимому начальству о том, что задача решается алгоритмически.

Увлекательная история о том, как в Pinterest Labs из одного набора данных четыре аналитика построили четыре очень отличающихся разбиения (https://medium.com/@Pinterest_Engineering/when-is-data-science-a-house-of-cards-86c9ab0a2c6f) напоминает анекдот про двух юристов в одной комнате, которые всегда приходят к трем взаимоисключающим абсолютно законным решениям одной задачи. Мораль - роль человека в анализе данных важна и лучшее, что может делать исследователь - изучать предметную область.

Метод Маринки Житник, от которого я лично в восторге, позволяет объединить в одной проекции сколько угодно сетей. Интерпретируемость полученных представлений можно повысить, например раскрасив проекцию, полученную с помощью алгоритма t-sne (да, мы тут пытаемся интерпретировать проекцию проекции), либо построив статистики для полученных кластеров.

Погрузиться в сетевой анализ можно, попробовав пройти курс от Леонида Жукова на русском языке (http://leonidzhukov.net/hse/2014/socialnetworks/), либо автора билиотеки SNAP Юре Лесковека (http://web.stanford.edu/class/cs224w/handouts.html). Последний обновляется ежегодно, дабы соответствовать состоянию дел на острие прогресса. А вообще, приходите к нам в чат (http://ods.ai/), там там есть канал #network_analysis


Лучший враг хорошего, или что-то вроде домашки