基于Spark Grahpx Neo4j 实现用户社群发现_spark graphx中介中心性

上一篇文章《知识图谱在大数据中的应用》我们介绍了知识图谱的一些概念和应用场景，今天我们就来看一个具体的应用案例了解下知识图谱的应用。用户增长对于一个APP的生存起到了至关重要的作用，没有持续的用户增长，再好的APP也不会走的长远，为了获得更多的用户，APP运营商往往会鼓励老用户拉新并给与奖励，比如趣头条的收徒模式，用户每收一个徒弟就会得到几块到十几块的现金返现，但是这种模式同时也会引起广大黑产团伙的注意，黑产会利用各种手段来薅这些APP运营商的羊毛。

中国有句老话，叫物以类聚，人以群分，在反作弊和市场营销等应用中，如果我们能根据用户间的某些联系发现社群，然后对这些社群进行反作弊分析或商品推荐，往往会起到意想不到的效果。

本文就来介绍一个简单的社群发现的实践。构建社群我们首先需要找到社群用户的某种联系，上文提到的收徒模式本身就是用户间的一个天然联系，我们可以根据用户的师徒关系来构建社群。如下图所示，根据师徒关系我们构建了一个社群，点表示用户，边表示师徒关系。

有了这样的社群之后，我们就可以基于社群维度分析设备及用户行为的异常，比如单个设备登陆过多的用户，设备一直处于充电状态，所有用户行为高度一致等，同时可以计算社群用户作弊率来通过已知作弊用户来发现新的作弊用户。

理清了需求之后我们开始着手根据用户师徒关系构建社群。对"紧密联系"的不同理解产生了很多社区发现算法。下图是几种经典的社群发现算法。

社群算法

1. Triangle Counting：三角关系，图论基础知识。
2. Connected Components：连通图，图论基础知识。
3. Strongly Connected Components：强连通图，图论基础知识。
4. Label Propagation：标签传播算法。
5. Louvain：一种基于"模块度"的经典算法。

因为本文重点不是讲述社群发现算法，所以这个算法具体的含义此处略过，有感兴趣的读者可自行研究。本文选用了最简单的连通图算法来实现社群发现，即只要两个节点之间有边我们就把它们归属为一个社群。下面我们进入根据用户师徒关系生成社群阶段。

Spark Graphx构建社群

Spark Graphx本身就提供了构建图并生成连通图的接口，我们只需要按要求输入数据就好了。如下图所示：

我们构建点和边，然后调用Graphx接口生成图，最后调用图的接口直接获取连通图。需要注意的是，Spark Graphx构建点和边时，id需要用Long类型的数字表示，所以我们需要维护一张用户id到数字id的维表。

//构建用户节点
val users: RDD[(VertexId, String)] =
      spark.sparkContext.parallelize(Array((3L, "u3"), (7L, "u7"),(5L, "u5"), (2L, "u2"), (4L, "u4"),(6L, "u6"),(8L, "u8")))

//构建用户边
val relationships: RDD[Edge[String]] =
      spark.sparkContext.parallelize(Array(Edge(7L, 3L,""), Edge(5L, 3L,""),Edge(5L, 2L,""), Edge(6L, 4L,""),Edge(8L, 6L,"")))

//组合节点和边构建图
val graph = Graph(users, relationships)

//从图中抽取出连通图
val components = graph.connectedComponents()

//获取连通图中的点，vertices是一个tuple类型，key分别为所有的顶点id，value为key所在的连通图id(连通图中顶点id最小值)
val vertices = components.vertices
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

得到的vertices是如下的k-v数据：

   /**
      * vertices：
      * (6,4)
      * (8,4)
      * (3,2)
      * (7,2)
      * (5,2)
      *
      * 是一个tuple类型，key分别为所有的顶点id，value为key所在的连通图id(连通图中顶点id最小值)
      */
1
2
3
4
5
6
7
8
9

然后我们将边relationships与vertices求出每条边所在连通图里顶点id最小值。

val result = relationships.map(x =>{
      (x.srcId,x.dstId.toString)
    }).join(vertices)
      .map(y =>{
        // (7,(3,2)) => (2,(7,3))
        (y._2._2,(y._1,y._2._1))
 }) 
1
2
3
4
5
6

我们将结果存入图数据Neo4j，可视化后如下所示，可以看到我们得到了两个社群。

至此，我们利用Spark Graphx构建出了社群，每个社群都有自己的一个社群id，然后我们就可以基于社群做一些具体分析了，比如，我可以计算社群作弊率，并取出TOP N的社群，如下所示。

想及时了解更多大数据实践，请关注我的公众号《大数据技术进阶》上面只是一个简单的示例，其实我们可以给点和边加上更多的属性，利用图的特性进行检索，可以更高效的检索出更多的信息。为了更方便的存储和查询社群内的数据，我们可以将社群存储到图数据库Neo4j。上面的社群图就是用Neo4j展示的，那么什么是Neo4j呢？下面我们简单的介绍下。

Neo4j简介

Neo4j是一个嵌入式的、基于磁盘的、具备完全的事务特性的图数据存储引擎。作为图数据库，Neo4j最大的特点是关系数据的存储。图数据库除了能够像普通的数据库一样存储一行一行的数据之外，还可以很方便的存储数据之间的关系信息。

例如，对于一个社交网络的用户数据库，你除了要存储每个用户的姓名、性别、喜好这些基本信息外，你还需要存储一个用户和哪些用户是朋友，和哪个用户是情侣这些关系数据，这个时候Neo4j这样的图数据库就可以派上用场啦。

通过下图，大家可以了解下什么是图数据库以及什么是关系数据。

在上图中，包含两个标签为"人"的数据节点，分别代表Ann和Dan两个用户。这两个数据节点还包含姓名、出生地等属性信息，用于表示两个用户的基本信息，就如同常规数据库中的两行数据。

除此之外，两个数据节点之间还包含两条关系数据，即Ann嫁给了Dan，Ann和Dan同居。利用这些关系数据，你就可以方便的作出基于关系的查询，例如你可以查询Ann跟谁结婚了，这就是图数据库的优势。

可能有人会说，上边写的这种关系数据结构，SQL也可以通过多表join等方法实现，那要Neo4j还有什么用？但毕竟术业有专攻，对于大量、复杂的关系数据处理，Neo4j在性能和使用方便程度上都是要远胜于SQL的。下边给大家简单总结下Neo4j的特点。

Neo4j的特点

• 像SQL一样的查询语言cypher
• 它遵循属性图数据模型
• 它通过使用Apache Lucence支持索引
• 它支持UNIQUE约束
• 它包含一个用于执行cypher命令的UI：Neo4j数据浏览器
• 它支持完整的ACID（原子性，一致性，隔离性和持久性）规则
• 它支持查询的数据导出到JSON和XLS格式
• 它提供了REST API，可以被任何编程语言（如Java，Spring，Scala等）访问
• 它提供了可以通过任何UI MVC框架（如Node JS）访问的Java脚本
• 它支持两种Java API：Cypher API和Native Java API来开发Java应用程序
• 支持高可用性主从集群部署。

Cypher语言

Cypher是Neo4j的图形查询语言，关键字大小写不敏感。语法和SQL很像，学起来相对简单。

• 基本格式
  MATCH WHERE RETURN
• 模式
  () 表示节点
  [] 表示关系，关系是有向的，连接的点分为源点和目标点
  {} 表示属性，每个属性通过key:value的形式表示，多个属性之间用逗号隔开，关系也可以有属性
• 标签
  用来标识一个节点属于哪一类。一个节点可以有多个或0个标签。标签没有属性。
  node:label1:label2 通过冒号给节点添加标签,通过冒号分隔多个标签
• 基本的增删改查

插入一个节点
CREATE (n:Person {name : 'Andres'});

插入一条边
MATCH (a:Person),(b:Person) WHERE a.name = 'Node A' AND b.name = 'Node B‘ CREATE (a)-[r:Follow]->(b);

更新节点
MATCH (n:Person { name: 'Andres' })  SET n.name = 'Taylor';

删除节点
MATCH (n:Person { name:'Taylor' }) DETACH DELETE n;

删除边
MATCH (a:Person)-[r:Follow]->(b:Person) WHERE a.name = 'Node A' AND b.name = 'Node B‘ DELETE r;

查询一个节点的所有Follow
MATCH (:Person { name:'Taylor' })-[r:Follow]->(Person) RETURN Person.name;

查询一个节点最短路径
MATCH (ms:Person { name:'Node A' }),(cs:Person { name:'Node B' }), p = shortestPath((ms)-[r:Follow]-(cs))     RETURN p;

清空数据库
MATCH (n) DETACH DELETE n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Neo4j数据浏览器

通过Neo4j浏览器就可以直接进行图的查询。

Cypher演示示例

我们使用Cypher查询语言对Neo4j中的一个家庭进行建模，包括年龄，性别和家庭成员之间的关系等个人属性。我们创建了一些朋友来扩大我们的社交图，然后添加键/值对来生成每个用户看过的电影列表。最后，我们查询了我们的数据，使用图形分析来搜索一个用户没有看到但可能喜欢的电影。

创建家庭成员节点及关系

CREATE (person:Person {name: "Steven", age: 45}) RETURN person
CREATE (person:Person {name: "Michael", age: 16}) RETURN person
CREATE (person:Person {name: "Rebecca", age: 7}) RETURN person
CREATE (person:Person {name: "Linda",age:40}) RETURN person
MATCH (steven:Person {name: "Steven"}), (linda:Person {name: "Linda"}) CREATE (steven)-[:IS_MARRIED_TO]->(linda) return steven, linda
MATCH (michael:Person {name: "Michael"}), (rebecca:Person {name: "Rebecca"}) CREATE (michael)-[:IS_SIBLILNG]->(rebecca) return michael, rebecca
MATCH (steven:Person {name: "Steven"}), (michael:Person {name: "Michael"}) CREATE (steven)-[:HAS_CHILD]->(michael) return steven, michael
MATCH (steven:Person {name: "Steven"}), (rebecca:Person {name: "Rebecca"}) CREATE (steven)-[:HAS_CHILD]->(rebecca) return steven, rebecca
MATCH (linda:Person {name: "Linda"}), (michael:Person {name: "Michael"}) CREATE (linda)-[:HAS_CHILD]->(michael) return linda, michael
MATCH (linda:Person {name: "Linda"}), (rebecca:Person {name: "Rebecca"}) CREATE (linda)-[:HAS_CHILD]->(rebecca) return linda, Rebecca
1
2
3
4
5
6
7
8
9

添加朋友节点及关系，组成社交网络

MATCH (michael:Person {name: "Michael"}) CREATE (michael)-[:FRIEND]->(charlie:Person {name: "Charlie", age: 16}) RETURN michael, charlie
MATCH (michael:Person {name: "Michael"}) CREATE (michael)-[:FRIEND]->(koby:Person {name: "Koby"}) RETURN michael, koby
MATCH (michael:Person {name: "Michael"}) CREATE (michael)-[:FRIEND]->(grant:Person {name: "Grant"}) RETURN michael, grant
MATCH (rebecca:Person {name: "Rebecca"}) CREATE (rebecca)-[:FRIEND]->(jordyn:Person {name: "Jordyn"}) RETURN rebecca, jordyn
MATCH (rebecca:Person {name: "Rebecca"}) CREATE (rebecca)-[:FRIEND]->(katie:Person {name: "Katie"}) RETURN rebecca, katie
1
2
3
4

添加电影节点及关系，并携带打分属性

CREATE (movie:Movie {title:"Avengers"}) RETURN movie
MATCH (michael:Person {name:"Michael"}), (avengers:Movie {title:"Avengers"}) CREATE (michael)-[:HAS_SEEN {rating:5}]->(avengers) return michael, avengers
CREATE (movie:Movie {title:"Batman"}) RETURN movie
CREATE (movie:Movie {title:"Gone with the Wind"}) RETURN movie
CREATE (movie:Movie {title:"Spongebob Square Pants"}) RETURN movie
CREATE (movie:Movie {title:"Avengers 2"}) RETURN movie
MATCH (charlie:Person {name:"Charlie"}), (movie:Movie {title:"Batman"}) CREATE (charlie)-[:HAS_SEEN {rating:4}]->(movie) return charlie, movie
MATCH (charlie:Person {name:"Charlie"}), (movie:Movie {title:"Gone with the Wind"}) CREATE (charlie)-[:HAS_SEEN {rating:0}]->(movie) return charlie, movie
MATCH (koby:Person {name:"Koby"}), (movie:Movie {title:"Batman"}) CREATE (koby)-[:HAS_SEEN {rating:4}]->(movie) return koby, movie
MATCH (koby:Person {name:"Koby"}), (movie:Movie {title:"Avengers 2"}) CREATE (koby)-[:HAS_SEEN {rating:5}]->(movie) return koby, movie
MATCH (grant:Person {name:"Grant"}), (movie:Movie {title:"Spongebob Square Pants"}) CREATE (grant)-[:HAS_SEEN {rating:1}]->(movie) return grant, movie
MATCH (jordyn:Person {name:"Jordyn"}), (movie:Movie {title:"Spongebob Square Pants"}) CREATE (jordyn)-[:HAS_SEEN {rating:5}]->(movie) return jordyn, movie
MATCH (michael:Person {name: "Michael"}) SET michael.gender = "male" RETURN michael
MATCH (rebecca:Person {name: "Rebecca"}) SET rebecca.gender = "female" RETURN rebecca
1
2
3
4
5
6
7
8
9
10
11
12
13

最后我们通过下面语句查询steven的孩子的男性朋友看过而且打分大于3分的电影

MATCH (steven:Person {name:"Steven"})-[:HAS_CHILD]-(child:Person)-[:FRIEND]-(friend:Person)-[hasSeen:HAS_SEEN]-(movie:Movie) WHERE child.gender = "male" AND hasSeen.rating > 3 RETURN DISTINCT movie.title

总结

本文主要介绍了利用Spark Graphx实现了一个简单的连通图社群发现示例，并将社群存入到图数据库Neo4j中，同时进一步介绍了Neo4j的一些概念和使用，最后用Neo4j演示了一个社交网络的图检索示例。