关于 省际加油竞争社团识别的方法研究

罗娅 1 张永成 1 侯平 2 陆艺 3 赵光娟 1

1 石化盈科信息技术有限责任公司  北京 100007

2中国石化销售股份有限公司 北京 100728

3南京光普信息技术有限公司 南京 210000

摘要：提出一种基于LOUVAIN算法识别不同省公司加油站之间存在组团加油规律的一种分析方法。通过对组团内用户加油规律变化的分析，统计组团内各省加油站当天净流入/流出的用户数，判定组团内竞争获利/损失的省（站），就省际竞争进行探讨，为各省油品销售负责人把握省际竞争态势及制定营销策略提供数据支持。

关键词：LOUVAIN算法；组团加油规律；省际加油竞争；省际竞争组团；

中图分类号： 文献标识码： 文章编号：

0 研究背景

随着交通的日益发达，加油站的竞争对手已经不仅仅局限于省内各加油站，省际竞争早已提上议程，而且省际竞争也是“新常态”发展动力之一，但由于省际加油的特殊性，各省油品销售负责人对省际竞争的具体竞争态势很难完全把握，因此造成了经营方面的被动。

针对这种状况，总部提出：不同省公司加油站之间是否存在某种加油规律？能否明确两省之间竞争问题，包括客户的流失以及由于邻省的竞争导致的本省的销量变化？

“不同省公司加油站之间”很明显可以归为一个社会网络问题，社会网络的研究关键在于节点间的关系与社会属性。现实表明,真实的社会网络都具有社区结构的特性, 而Louvain社区发现就是通过网络中节点间的连接关系挖掘社区结构的过程，是目前行业内最常用的社区发现算法之一：张子乔的硕士论文就基于Louvain算法对社团结构划分进行了研究^[10]，李沐南在其硕士论文^[6]中，对Louvain算法在社区挖掘中的研究与实现进行了研究并提出了改进，吴祖峰等^[11]也基于Louvain算法对社团划分进行研究并提出改进。

作为一种基于模块度的图算法模型，与普通的基于模块度和模块度增益不同的是，Louvain社区发现算法速度很快，而且对一些点多边少的图，进行聚类效果特别明显，非常契合“不同省公司加油站之间”呈现出的社区结构，而且目前省际加油竞争这个领域并没有深入的研究以供借鉴，鉴于此，本文尝试从社会网络方面研究入手，采用Louvain算法识别加油站组团，通过对组团内用户加油规律变化的分析，统计组团内各省加油站当天净流入/流出的用户数，判定组团内竞争获利/损失的省（站），就总部提出的问题进行探讨，为各省油品销售负责人把握省际竞争态势及制定营销策略提供数据支持。

1 Louvain算法简介

本文所用的算法为Louvain算法，一种基于模块度（Modularity）的社区发现算法，它的优点是快速、准确，并且能够发现层次性的社区结构，被文献^[2]认为是性能最好的社区发现算法之一。算法的优化目标为最大化整个图属性结构（社区网络）的模块度。

1.1模型评价

1）模块度

模块度是评估一个社区网络划分好坏的度量方法，它的物理含义是社区内节点的连边数与随机情况下的边数之差，它的取值范围是 [− ,1)，其定义如下：

（1.1）

其中，

①A_ij 表示节点 ,j之间的连边权重，网络是非带权图时，所有边的权重可以看作是1；

② 为图中边的总数量，即所有边的权重之和（边的数目）；

③k_i表示所有指向节点 的连边权重之和，k_j表示所有指向节点j的连边权重之和；

④c_i表示节点 所属的社区；

⑤ 函数表示若 与j在同一个集群里，则返回值是1，否则返回0，即

公式（1.1）中 = ，节点j连接到任意一个节点的概率是 ，现在节点 的度数为 ，因此在随机情况下节点 与j的边为 ，模块度的公式定义可以做如下简化：

(1.2)

其中 表示社区C内的边的权重之和， 表示与社区C内的节点相连的边的权重之和。

一轮迭代之后，如果整个Q没有变化，则停止迭代，否则继续迭代。

2）模块度增益

（1.3）

通俗的讲即为：社区C加入节点 之后的模块度-（社区C原始的模块度+节点 原始的模块度）

化简可以得到

（1.4）

其中 是社区C内节点与节点 的边权重之和^[7]。

在第一阶段，判断一个节点加入到哪个社区，需要找到一个最大的ΔQ 。

1.2 Louvain算法原理

Louvain算法分为两个阶段，两步迭代设计如下：

① 将图中的每个节点看成一个独立的社区，算法扫描图中的所有节点，针对每个节点遍历该节点的所有邻居节点，衡量把该节点加入其邻居节点所在的社区所带来的模块度的收益，并选择对应最大收益的邻居节点，加入其所在的社区。这一过程化重复进行，直到每一个节点的社区归属都不再发生变化。

② 对步骤①中形成的社区进行折叠，把每个社区折叠成一个单点，社区内节点之间的边的权重转化为新节点的环的权重^[8]，社区间的边权重转化为新节点间的边权重，分别计算这些新生成的“社区点”之间的连边权重，以及社区内的所有点之间的连边权重之和，用于下一轮的步骤①。

2 应用案例

2.1 样本选择

本文选取的数据集为2020年5月11日-6月9日之间的数据，识别这段时间内每2个加油站间共享的持卡加油用户，剔除共享用户数在10人以下的站点对（注：观察长周期的用户数据，研究发现30天内共享人数不足10人的站点对，其共享用户没有稳定的加油行为规律），得到清洗后的数据样本^①，包括加油站点对，及其对应的共享用户群组。

2.2算法过程

1）首先，基于样本^①，采用LOUVAIN算法识别加油站组团，具体算法过程如下：

① 将每一个加油站看作一个独立组团；

② 依次将每个加油站与其它加油站合并，根据公式(1.2)计算模块度；

③ 针对合并后的新组团，根据公式(1.4)计算模块度增益，选取该加油站对应模块度增益最大的组团，把加油站加入到该组团中；

④ 对所有加油站组合重复②③，直至每一个加油站所属组团不再发生变化；

⑤ 将组团压缩为一个节点，再次重复②-④的步骤，直至算法稳定。

由此得出的组团具有如下加油特征：每一个用户在组团内游走的概率均大于在组团外，因此可以认为用户在组团内的游走是有规律的，游走到组团外的行为是无规律的（偶发的），每个加油站组团内的共享用户在组团内加油的概率均大于在组团外加油站加油的概率。

2）接下来，根据组团结果及2020年5月11日-6月9日这段时间内的加油数据，剔除加油站组团内用户在组团外加油的记录，获得计算样本^②；

3）同时，识别组团内用户的归属省/加油站，即用户30天内在A省/A_i加油站加油的升数超过其总加油升数的60%，则定义该用户归属A省/A_i加油站；

4）最后，根据样本^②，结合用户的归属省/加油站，统计每个加油站当天流入的加油升数：

① 统计组团内两省加油站当天从对手省获得的净流入的升数，判定组团内竞争获利/损失的省（销售公司）

② 统计同省加油站当天从对手省获得的净流入的升数，判定竞争获利/损失的省（销售公司）

2.3 结果解读及系统实现

以省A为例分析2020年06月10日当天的竞争情况：（红色代表获利方，绿色代表损失方）

总体来说，与省A发生了竞争的企业有省B、省C、省D、省E、省F、省H ，其中省B、省C是损失方，人群从省B、省C流入到省A；省D等是获利方，人群从省A流失到省D等。

2.3.1省际竞争指数代表的含义：

①省A与省D的竞争指数-1735.93：代表当天省D从省A获利了1735.93 升的油量（即省A从省D获得的油量与省D从省A获得的油量之差）；

②省A与省C的竞争指数152.51 ：代表当天省A从省C获利了152.51升油量。

2.3.2组团内加油站竞争指数代表的含义：

站在省A的角度，以省A与省D为例，省A与省D之间发生了竞争，存在一些竞争组团（竞争组团分获利组团和损失组团）

1) 组团有些是获利的,如下图所示；

该组团内只有获利组团G001

①组团内包含2个油站：加油站A1 、加油站D1；

②加油站A1指数596.96，代表属于加油站D1的用户当天到加油站A1消费了596.96升；

③加油站D1指数214.59，代表属于加油站A1的用户当天在加油站D1消费了214.59升；

加油站A1总计获利382.37升

2）损失组团，总计损失2118.3升,如下图所示:

该组团内，包含三个损失组团，以损失组团D001为例：

①组团内包含2个加油站：加油站A4，加油站D4；

②加油站A4指数0.00 ，代表当天没有属于加油站D4的用户到该站消费；

③加油站D4指数2053.74，代表加油站A4的用户当天到加油站D4消费了2053.74升；

该组团中，省A合计损失2053.74升。

最终，站在省A的角度，统计所有获利组团和损失组团，总体上，省A损失了1735.93升。

3 总结与展望

本文通过LOUVAIN算法识别出了不同省公司加油站之间存在的组团加油现象，对由于邻省的竞争导致的本省客户的流失以及销量变化进行了初步的探讨，并形成系统，做到了展现查询日期当天的持卡消费人群转移情况（仅支持两两省份分析）。

各油品销售负责人可以根据组团结果及人群转移情况，结合加油站地理位置等因素，分析原因，制定相应的经营策略。

目前，在加油站省际竞争方面，研究非常少，本文提出的方法也是一种尝试性的探索，需要在实践中检验并不断完善。

参考文献

[1] Vincent D.Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre. Fast unfolding of communities in large networks, Journal of Statistical Mechanics: Theory and Experiment,1742-5468, P10008,2008

[2] Andrea，Lancichinetti，Santo，Fortunato. Community detection algorithms: A comparative analysis. Physical Review E

[3] Clauset, Aaron，Newman, M. E. J，Moore, Cristopher. Finding community structure in very large networks. Physical Review E,2004

[4] Louvain社区发现算法[Z].博客园.

[5] Louvain算法原理及设计实现[Z].简书

[6] 李沐南.Louvain算法在社区挖掘中的研究与实现[D].中国石油大学(北京)

[7] Louvain算法的介绍与利用Graphx的实现过程[Z].简书

[8] Newman M. Modularity and community structure in networks[C]//APS March Meeting. American Physical Society,2006:8577-8582

[9] 胡健，薛龙龙.基于用户特征和链接关系的Louvain算法研究[J]. 计算机与数字工程

[10] 张子乔.基于Louvain算法的社团结构划分[D].华东师范大学

[11] 吴祖峰，王鹏飞，秦志光，蒋绍权.改进的Louvain社团划分算法[J].电子科技大学学报 2013