社交网络分析与机器学习

谈到数据科学,你会想到机器学习和数据挖掘,但是你应该考虑将社交网络分析作为数据科学工具包的一部分。社交网络分析通过使用图和网络来映射和测量关系,提供了从你的数据集中捕获特征的新方法,并且它是对传统机器学习技术,如聚类分析,的补充。

让我们用一个例子来展示它是如何工作的。这篇文章解释了Facebook是如何知道你什么时候离婚的(甚至在你之前)。不幸的是,我们无法访问Facebook拥有的数据集,但是我们可以使用公开的数据集进行类似的分析。

Zachary’s的空手道俱乐部数据集

Zachary的空手道俱乐部数据集包含了20世纪70年代美国大学空手道俱乐部34名成员之间的社交网络。我们不知道细节,但是这个俱乐部爆发的一场争端最终导致了它分成两组。我们能通过观察类似Facebook的社交关系结构来准确预测俱乐部会如何分裂吗?

让我们加载数据集

您可以在此下载数据集,但它是一种不熟悉的非表格文本格式。我创建了一个加载数据的脚本来解析这个文本文件,但是你可以直接加载MAT文件

load karate.mat

创建图对象

单个成员表示为节点,连接两个节点的边表示他们的友谊。因此,边只是一对节点。边表示成78×2矩阵中的行。节点只是代表节点的数字数组。友谊是相互的,因此没有方向。我们可以用无向图来表示这个社交网络。您可以通过提供形成边的节点列表来创建图。

G = graph(edges(:,1), edges(:,2)); % create a graph from edges

G.Nodes = table(name); % name the nodes

figure % visualize the graph

plot(G);

title('Zachary''s Karate Club')

https://blogs.mathworks.com/images/loren/2015/breakup_01.png

谁是联系最多的人?

该图显示了一个典型的“中心和辐条”结构,其中有几个中心,这些中心是具有大量连接的节点。如果你有很多朋友,你会很受欢迎,所以这代表受欢迎度。量化受欢迎程度的一种方法是一种称为度的度量,即连接到每个节点的边数。让我们找到这个社交网络的度分布。

D = degree(G); % get degrees per node

mu = mean(D); % average degrees

figure

histogram(D); % plot histogram

hold on

line([mu, mu],[0, 10], 'Color', 'r') % average degrees line

title('Karate Club Degree Distribution')

xlabel('degrees (# of connections)'); ylabel('# of nodes');

text(mu + 0.1, 10, sprintf('Average %.2f Degrees', mu))

text(14.5, 1.5, 'Node 1')

text(11, 2, 'Node 33')

text(16, 2, 'Node 34')

https://blogs.mathworks.com/images/loren/2015/breakup_02.png

你可以看到两个人(节点1和34)的度数远高于平均度数。节点33有很多朋友,但没有这两个朋友多。让我们给这两个人的边(连接)上色。

N1 = neighbors(G, 1); % get 1's friends

N1 = [N1; 1]; % add 1

N34 = neighbors(G, 34); % get 34's friends

N34 = [N34; 34]; % add 34

c1 = [1,0,1]; % 1's group color

c2 = [0,1,0.5]; % 34's group color

figure

P = plot(G); % plot the graph

highlight(P, N1, 'NodeColor', c1, 'EdgeColor', c1); % highlight 1's friends

highlight(P, N34, 'NodeColor', c2, 'EdgeColor', c2);% highlight 34's friends

title('Friends of Nodes 1 and 34')

https://blogs.mathworks.com/images/loren/2015/breakup_03.png

分裂

通过给这两者的连接着色,你可以看到俱乐部已经有了基于社会关系的两个小群。让我们根据上述链接的教科书中的信息,将之前的可视化与实际分手的可视化进行比较。

G1nodes = [1, 2, 3, 4, 5, 6, 7, 8, 9,... % Node 1's group

11, 12, 13, 14, 17, 18, 20, 22];

figure

P = plot(G); % plot the graph

highlight(P, G1nodes, 'NodeColor', c1,'EdgeColor', c1); % highlight group

title('The club broke up in two groups')

https://blogs.mathworks.com/images/loren/2015/breakup_04.png

预测分裂

现在我们已经熟悉了这个数据集,让我们看看是否有办法检测这个数据集中的两个组。这是这个网络的邻接矩阵。每一行和每一列都是节点标识,如果两个节点有关系,则交集变为1,否则为0。对角线元素代表自我连接,因此在这个社交网络中它们是0。

A = adjacency(G); % create adjacency matrix

A = full(A); % convert the sparse matrix to full matrix

figure

imagesc(A) % plot the matrix

axis square

title('Adjacency Matrix')

https://blogs.mathworks.com/images/loren/2015/breakup_05.png

分层聚类方法

在机器学习中,这可以作为聚类问题来处理。让我们尝试使用共享连接数作为距离度量的分层聚类——共享的连接数越多,距离越近。由于我们有二进制数据,我们将使用Jaccard距离。

dist = pdist(A, 'jaccard'); % use Jaccard distance to score connections

Z = linkage(dist); % create tree

figure

dendrogram(Z) % plot dendrogram

title('Dendrogram Plot')

xlabel('Node Id'); ylabel('Distance')

https://blogs.mathworks.com/images/loren/2015/breakup_06.png

这看起来不太对,因为它完全忽略了网络中的连接结构。这是一个很好的例子,传统的机器学习方法无法单独解决这个问题。

图划分方法

根据图论,我们可以用什么来划分图?PatQuillen建议的一种方法是使用代数连通性根据创建两个子集所需的最小切割次数对节点进行加权,FielderVector用于此目的。在典型的使用中,我们希望将节点划分成两组大小相等的节点。让我们用中值来划分节点。值低于中值的节点与值较高的节点相比,连接性较差。

现在让我们使用FielderVector来识别图形分区,并将结果与实际分割进行比较。

L = laplacian(G); % get Laplacian Matrix of G

[V, ~] = eig(full(L),'vector'); % get eigenvectors from L

w = V(:,2); % the Fiedler Vector

P1nodes = find(w < median(w)); % select nodes below median value

errors = setdiff(G1nodes, P1nodes) % any diff from the actual split?

errors = Empty matrix: 1-by-0

你可以看到FielderVector在识别这个图的分区方面做得非常好。如果你按FielderVector对邻接矩阵排序,你也可以看到这种分割。

[~, order] = sort(w); % sort the weights by value

sortedA = A(order, order); % apply the sort order to A

figure

imagesc(sortedA)

title('Sorted Adjacency Matrix')

https://blogs.mathworks.com/images/loren/2015/breakup_07.png

总结——这与Facebook的例子相比如何?

在这种情况下,我们只需要FielderVector来划分图。但是在更复杂的情况下,你可以用它作为聚类分析的距离度量,代替上面例子中的Jaccard距离。社交网络分析和机器学习应该是数据科学工具包中的补充工具。

这如何适用于Facebook预测夫妻分手的情况?将节点1和节点34视为一对夫妇,将图视为他们的Facebook好友。它看起来与上面引用的文章中的图惊人地相似,只是它有两个以上的集群。如果你仔细想想,你有老同学、同事、家庭成员和其他社交活动,他们通常会形成不同的群体。

有趣的是,这篇文章说,夫妻共有的共同朋友的总数并不是浪漫关系的好指标。如果他们共同的朋友连接较少,那更好一点。显然,浪漫关系和空手道俱乐部并不共享同样的社会动态。

广告

0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论