在Instagram上识别跨社区以识别用户兴趣

社交网络上的个人资料可以告诉一个人多少？ 照片，帖子，评论，订阅-用于分析的原始字段。 今天，我们将讨论如何根据用户的Instagram订阅来确定用户的兴趣。

来源

一种明显的方法是对一个人的订阅进行分类。 例如，在用户Ivan的订阅中，我们发现了两个自动博客和三个带有有趣图片的帐户，其余的个人资料不是主题的（我们假设这些人是朋友，亲戚，同事等）。 由此我们得出结论：伊万是一个开朗的人，喜欢汽车。 获利 我们所需要的只是对应的“ blogger +内容主题”，但是这里并不是所有的事情都那么简单。

谁是博客作者？ Instagram上的博客与普通帐户没有什么不同（通常，它就像一种心理状态）。 理想情况下，我们对拥有大量现场观众的主题账户感兴趣，尽管我们不想简单地减少订阅者的数量，但我们可能会错过一些东西。

在哪里获得良好的分类法？ 如果您自己提出类别，那么一定会在“不同的事物”中迷失一些有趣的东西，并且当一切准备就绪时，事实证明类别太宽泛了。 我们希望得到一个自然的分区，因此我们将群集博客作者。

一个博客作者可以属于几个类别吗？ 就这样！ 通常，他同时是瑞士人，收割者和花花公子玩花花公子（以及旅行，生活方式，妻子和母亲）。
因此，我们需要一个拥有大量博客作者的数据集以及一个在输出处具有相交群集的群集算法。

一切如何开始

想要与最有效的Instagram上的意见领袖放置广告的客户联系我们。 有时有一个博客列表，然后我们解决优化问题-以更少的钱吸引更多人，有时没有列表，需要找到相关的博客。 这次，他们搜索了眼科医生的资料。

我们使用了一种类似于推荐系统的方法：

1. 用手选择3-7个合适的个人资料（“核心社区”）
   
   
   
   
2. 使用订户的交集，我们识别出对该主题感兴趣的人（“热情”）
   
   
   
   
3. 我们正在寻找“热情”人士的新医生
   
   
   
   
   
4. 如有必要，重复步骤1-3（将新医生添加到“核心”或进行更改）
   

现在更详细地讲一个例子。

步骤1.使用Instagram搜索，我们选择了来自俄罗斯不同地区的6位眼科医生：


列表是随机的，但是对于我们来说，博客确实符合主题就足够了，订阅者不少于1000人。

步骤2.跨过所有订户后，我们看一下分布。

万岁！ 有路口。

此外，有两个人已订阅全部六个个人资料！ 因此，现在您需要确定我们认为谁是“热情”眼科专家。 我们决定从三个订阅开始吸引所有人。 就像他们说的那样，1次是事故，2次是巧合，3次是规律。 因此，发现了131（2 + 3 + 24 + 102）个“热情”用户。

步骤3.下载“热情”人士的订阅，然后以各种可能的方式再次汇总。


我们得到了令人印象深刻的账目清单，现在我们将从中选择新的眼科医生。 右列显示在第二步中选择的131个人中有多少人已订阅该个人资料。 顶部是我们最初的六个配置文件，这不足为奇。 如果我们现在选择一个阈值并说：“所有计数值都超过十的个人资料都是新医生，”那么我们就有可能将眼科医师像Olga Buzova这样的热门帐户归因于眼科医师，同时会丢失少量但相关的个人资料，因此请多添加一个列订阅者数量，并计算订阅者中的热情用户百分比。


为了方便起见，该分数乘以100（因此，份额实际上是百分比）。 结果，在条件计数> = 6且份额> = 0.05的情况下，共接收了166位新的眼科医生。 上课！

第4步。172个帐户成为社区的新“核心”，这帮助找到了500多名新的眼科医生，但结果已经转移到了外国帐户。

Instagram推荐中的类似帐户

当然，这都很有趣，现在我们知道了如何查找彼此相似的帐户，但是我们仍然梦想将所有安装程序按类别进行分类。 然后我想到这个想法，看看现成的instagram建议。


事实是，专题报告有建议，但普通百姓却没有。 这是谁考虑博客作者的问题的答案，并且可以避免一次头痛。 万岁！

在建议中，一位博客作者拥有多达80个相似的个人资料。 我们从1000个俄罗斯博客列表开始。 他们采取了类似的措施，然后采取了类似的措施，然后……嗯，您明白了：

计划是有一天​​这一过程将结束，因为建议中将不会包含具有数百个订户的小型个人资料，但是当耐心结束时，我们实际上停止了。 您总是可以继续收集数据集，但是到目前为止，它并没有派上用场，很有可能我们已经涵盖了几乎所有俄罗斯博客，而且还可以。

现在，我们有了一个具有3,428,453个顶点（博客）和96,967,974个边（两个博客之间的相似度）的图形。

这就是我们的图在很小的样本上的样子

顺便说一句，事实证明我们并不是第一个选择这种方法的人。

显然，Instagram上的推荐是根据仍在关注此个人资料的关注者而形成的，因此，来自Bryansk的医生会在推荐中拥有受欢迎的Bryansk帐户和其他医生。 这类似于我们对眼科医生的搜索，但是现在我们可以考虑博客作者同时属于的所有社区。 此外，由于无需分析所有博客作者的订阅者，因此处理速度将大大提高，仅需推荐80个帐户即可。

算法的选择和描述

太好了！ 数据已经准备好了，现在我们需要选择一种工具和一种算法，可以处理这么大的图形，最好在足够的时间内处理。 让我提醒您，在输出时，我们希望获得一组社区，一个博客作者可以隶属于其中几个社区。

我们选择了斯坦福网络分析平台（SNAP）库

斯坦福网络分析平台（SNAP）是通用网络分析和图形挖掘库。 它用C ++编写，可以轻松扩展到具有数亿个节点和数十亿个边缘的大规模网络。 它有效地处理大型图，计算结构特性，生成规则图和随机图，并支持节点和边上的属性。

我们的注意力吸引到了AGMfit算法（AGM-关联图模型），结果，我们使用了BIGCLAM（大型网络的集群关联模型）。 它们的不同之处仅在于：在第一种情况下，组合解决了优化问题，这使其可扩展性降低，第二种情况仅允许您提供类似于我们的图。

主要且相当直观的想法：两个节点具有共同的社区越多，这两个节点之间进行通信的可能性就越大。 两种算法都基于Affilated Graph模型，因此让我们对其进行更详细的介绍：

假设我们有一个二部图，其中圆峰是社区（ $$和 $$$B$ ）和正方形-社交网络的用户，以及每个人（ $$$u$ ）是指具有特定权重的不同社区（ $$$F_ {uA}$ 和 $$$F_ {uB}$ ） 权重越大，参与者与社区其他成员联系（熟悉）的可能性就越大。


示例：在同一所大学学习的同事在Instagram上彼此关注。 他们俩都是同一所大学（社区1）的毕业生，并且在同一家公司（社区2）工作，我们不知道是什么原因造成了网络上的“友谊”，以及他们何时会面。 让一个刚从大学毕业并找到工作，再让第二个毕业生在五年前一直在公司工作，那么属于第一个社区1的权重就会增加，而属于第二社区1的权重就会减少，反之亦然。

对于每个由几个人组成的共同社区，我们有一个独立的机会来熟悉：

$$

$$1-exp（-F_ {uc} \ cdot F_ {vc}）$$

因此，社区越常见，他们彼此了解的可能性就越大：

$$

$$1-exp（-\ sum_c F_ {uc} \ cdot F_ {vc}）$$

如果我们计算每对用户之间建立连接的可能性，那么在输出处，我们将得到一个图形，其中顶点是人，而顶点之间的边是相识或彼此订阅的事实。

因此，从左侧的视图中，我们移至右侧的图片。


现在让我们了解如何在社区发现中使用此模型。

我们有一个类似博客作者的图表，我们的目标是发现 $$$K$ 社区使用上述模型，通过选择最合适的权重矩阵 $$$F$ （其尺寸 $$$N$ 上的节点 $$$K$ 社区），以便在输出处获得的图形与我们原始图形相似。 这通过最大化似然函数来完成。

$$

$$l（F）=对数P（G | F）$$

但是，这整个过程可以表示为非负矩阵分解，与AGMfit相比，BIGCLAM算法的可伸缩性有所提高。

在这里和这里阅读更多。

社区编号和启动

在BIGCLAM中，您可以指定社区的确切数量和间隔。 该算法会在每次测试中选择20％的节点对，并且将具有不同社区数量的模型调整80％。

我们形成了带有边列表的输入文件并运行：

./bigclam -o:bloggers -i:query_graph_all.edgelist -c:-1 -nc:20 -mc:50000 -xc:200000 -nt:10 

这些参数使您可以指定尝试次数，团体的最小和最大数目（或者，如有必要，可以是精确的数目），用于并行化的线程数和输出文件的前缀。 在我们的案例中，我们将10个线程尝试20次的间隔设置为50到20万个社区。 在2个Intel®Xeon®Gold 6150 CPU @ 2.70GHz上，所有这些出色表现被认为是5天。 输出收到两个文件，一个文件用于Gephi，第二个文本，其中每一行都是一个社区。

实际上，我们运行了两次算法，第一次遇到了5万个社区的上限，结果还不错，但是经常遇到混合社区。 这次，我们再次达到了20万个社区的最大值，但是它们变得更好了，我们在此止步。 您可能会得到更好的结果，但是二十万个未命名的社区使我们难以想象。

美丽的图画

现在如何处理所有这些？

一方面，由此产生的社区可帮助我们快速搜索狭窄的博客作者群体（当时与眼科医生一样）。 如果有几个博客作者为例，那么我们将其归入所有社区，丢弃不必要的社区，仅此而已。 您可以按名称使用搜索，例如，有关装饰和室内设计的社区之一：


另一方面，为了确定用户的利益，必须以某种方式有意义地调用所有这些社区。 或者，也许所有这些都是不必要的。

克拉克

不幸的是，并不是所有收到的社区都一样好，为了找到最有趣的社区，我们决定尝试使用同一SNAP库中的CRank优先级排序方法。 它旨在根据图表的结构自动匹配每个社区的排名：值越大，社区越好。

在计划的输入中，我们提交我们先前发现的社区，针对每个社区，计算优先级度量标准（4个），然后将这些度量标准汇总，然后得到一个估计值。


在这里阅读更多。

发射

 ./crank -i:bloggers_cmtyvv.txt -c:query_graph_all.edgelist -o:bloggers_prioritization.txt 

在发布过程中，他们遇到了与Ubuntu 18.04的兼容性问题， 他们在此处提供了一个解决方案。

由于我们的bloggers_cmtyvv.txt社区文件和edge_query_graph_all.edgelist列表最初包含昵称（字符串类型），因此我们必须对它们进行哈希处理，使其为int，否则便发誓。

让我们来看一个例子：

根据计划，我们将选择几个社区，在这些社区中，配置文件名称中包含字符串“ lokomotiv”，这应该是Lokomotiv俱乐部的足球迷社区，让我们看看它的真实含义。 社区成员用红色标记，每张图片下方都有一个相应的分数。

社区1，得分0.4
社区2，得分0.41
社区3，得分0.34
社区4，得分0.13

然后，在查看了此子图中的所有配置文件之后，我们选择了真正属于所需社区的人，结果如下所示：

事实证明，前两个社区实际上包含了我们所需要的内容，几乎没有错误（俄罗斯足球队俄罗斯的概况除外），第三个社区很好，但是覆盖的帐户少于前两个社区，因此得分较小，第四个社区，尽管它包含有关足球主题的信息（这里是其他俱乐部的球员，他们的妻子和管理人员），但是，它不适合我们。
我们可以得出结论，CRank的效果很好。

手动标记颜色和结果。

为了解决按兴趣为用户着色的问题，我们还分析了帖子的文本，我们希望查看结果在哪里更好/更有趣（在文本或订阅中）以及是否有匹配项。 对于一小部分人，必须独立标记大约800个社区。 我们对结果感到非常满意，并决定应该开发这种方法。 社区检测方法使您可以找到非常狭窄且与众不同的兴趣类别，例如，订阅老鼠的资料（在小型灰色啮齿动物的意义上）和其他令人惊奇的事物，您可以找出一个人应该对哪种运动感兴趣，而不必将所有内容都归入“极端”类别依此类推

我们可能不会标记所有20万个社区，但是也许我们会处理CRank结果，只留下高速的社区，也许我们会在必要时标记它们。 这样的事情:)

谢谢你

本文是与我的主管Artyom Korolev（ korolevart ）研发Dentsu Aegis Network Russia共同撰写的

来源