基于微信聊天记录时间信息的人物关系刻画技术研究

引用本文

康艳荣, 赵露, 范玮, 张紫华. 基于微信聊天记录时间信息的人物关系刻画技术研究[J].刑事技术, 2018,43(3):187-192
KANG Yanrong, ZHAO Lu, FAN Wei, ZHANG Zihua. Digital Profiling: Relationships Analysis Based on Time Information of Wechat[J]. Forensic Science and Technology,2018,43(3): 187-192 复制到剪切板

doi: 10.16467/j.1008-3650.2018.03.003
Permissions

《刑事技术》编辑部

基于微信聊天记录时间信息的人物关系刻画技术研究

康艳荣¹, 赵露¹, 范玮², 张紫华³

1.公安部物证鉴定中心,现场物证溯源技术国家工程实验室,痕迹科学与技术公安部重点实验室,北京 100038

2.天津市公安局物证鉴定中心,天津 300384

3.北京中伦文德律师事务所北京100028

第一作者简介：康艳荣（1980—）,女,河北乐亭人,硕士,副研究员,研究方向为电子物证。E-mail:kangyanrong@cifs.gov.cn

基金资助: “十三五”国家重点研发计划项目(No.2017YFC0803805); 公安部科技强警基础工作专项项目(No.2016GABJC22)

摘要

以微信为代表的通信工具每天都在产生可以描述人物关系的海量数据,如何通过数据整合为侦查办案提供智力资源和知识服务已成为大数据环境下公安机关科研工作的研究重点和难点内容。本文以微信聊天记录的时间信息为研究对象,利用分层聚类和K-均值聚类分析技术,发现通信时间特征与人物关系之间的关联关系,将微信联系人按照“亲疏远近”的人物关系进行分类,从而为案件侦查过程中快速寻找犯罪团伙、重点嫌疑对象提供一种新的技术手段。

关键词: 微信; 数据挖掘; 聚类分析; 时间特征; 人物关系刻画

中图分类号:DF793.2 文献标志码:A 文章编号:1008-3650(2018)03-0187-06

Digital Profiling: Relationships Analysis Based on Time Information of Wechat

KANG Yanrong¹, ZHAO Lu¹, FAN Wei², ZHANG Zihua³

1. Institute of Forensic Science, Ministry of Public Security, Beijing 100038, China

2. Institute of Forensic Science, Tianjin Municipal Public Security Bureau, Tianjin 300384, China

3. Zhonglun W&D Law Firm, Beijing 100028, China

Abstract

Wechat, presently one of the most popular communication tools, is everyday generating huge quantity of data that can be used to profile people’s relationship. Therefore, it is becoming the research focal points, albeit also difficult to attain, that how to integrate and mine the massive data is about to provide intelligent source and knowledge service for criminal cases investigation. In this paper, the time information was taken as the studied subject that was extracted from the Wechat’s record so that the relationships of Wechat’s contractors can be classified through finding the correlative time characteristics by Hierarchical clustering and K-means clustering analyses. Thus, this research is potential of providing new resorts for quickly searching criminal gangs or key suspects during case investigation.

Key words: Wechat; data mining; clustering analysis; time characteristics; social relationship

文章图片

数据的爆炸增长、广泛可用和巨大数量使得我们的时代成为真正的数据时代, 急需功能强大的工具从海量数据中发现有价值的信息, 并把这些数据转化成有组织的知识^[1]。经过近几十年的发展和完善, 数据挖掘技术已经日益成熟, 其主要方法有关联规则挖掘、分类与预测、聚类分析、遗传算法、文本挖掘、Web挖掘等^[2]。社交工具及应用作为新兴媒体的代表, 其本身所携带的社交信息、交流信息以及社交用户产生的大量文本、图像、音频、视频等内容对于数据挖掘来说又是挑战^[3]。现在流行的在线社交工具如推特、脸书、博客、微博、微信等通常都含有大量的链接数据和内容数据, 其中链接数据主要为图形结构, 表示两个实体之间的通信, 而内容数据则包含有文本、图像以及其他网络多媒体数据^[4]。以海量数据为支撑的对人物关系的量化研究正日益得到重视。目前, 基于链接的分析主要致力于链接预测^[5]、社区发现^[6]、社交网络进化^[7]和社会影响分析^[8]等领域; 而基于内容的分析主要聚焦于关键字搜索、分类、聚类和异构网络中的迁移学习^[9]等方面。近年来, 有学者不断提出了基于新方法的人物关系的定量分析, 如基于聚类分析（依据距离和相关系数来评估不同样本在属性上的相似性）与关联分析（分为同类事件的简单关联和不同事件的次序关联）的方法获取人物关系等^[10], 也有学者利用关系抽取技术, 扩展传统的二元关系, 提出了一种基于同义词词林的抽取关系描述词的方法, 并通过该方法在收集一定量特定领域内的人物关系信息的条件下实现人际网络的定量分析及结果的可视化^[11], 这在一定程度上促进了人物关系刻画技术的发展。本文在前人及笔者之前的研究^[12]基础上, 以微信聊天记录的时间信息为研究对象, 首先对微信聊天记录数据进行预处理, 包括文件格式转换、数据结构定义、计算变量选取, 接着按照微信聊天形式将其抽象为会话段数、会话时长和响应时间三个要素并使用聚类算法对其进行量化研究, 最后对使用不同算法得到的数据结果进行了对比分析, 发现了会话段数与联系紧密度、响应时间与联系倾向性等关系, 为案件侦查过程中快速寻找犯罪团伙、重点嫌疑对象提供了一种新的技术手段。

1 数据预处理

1.1 数据定义与变量设定

定义1.1 秒差：接收者从接收到上一条会话时间至发送出本条会话时间的时间差, 秒差的取值范围为0~N（N≥ 0）。

定义1.2 首次响应时间：一段会话中接收者首次对接收的最近一条会话进行响应所花费的时间。

定义1.3 一般响应时间：一段会话中除首次响应时间之外的发送者和接收者之间的所有会话所花费时间之和的平均值。

定义1.4 会话时长：一段会话中发送者和接收者之间的所有会话所花费的时间和。

定义1.5 会话段数：按照番茄工作法, 将发送者和接收者之间的聊天记录以20 min为一个时间段进行划分。

定义1.6 会话总时长：所有会话段数的会话时长之和。

定义1.7 首次响应时间均值：发送者和接收者所有会话段数中的首次响应时间和的平均值。

定义1.8 一般响应时间均值：发送者和接收者所有会话段数中的一般响应时间和的平均值。

定义1.9 未响应次数：20 min内单独存在的一条会话的个数。

1.2 数据预处理

本文选取机主Andy与其78个微信好友的聊天记录数据为实验数据, 在SPSS软件中使用如下命令进行数据预处理：

1）将会话按条进行编号：“ COMPUTE 会话编号=$CASENUM. EXECUTE.” 2）计算变量“ 秒差” ：“ COMPUTE 秒差=发送时间 - LAG(发送时间). EXECUTE.” 3）将“ 秒差” 大于20 min的该条会话标记为一段会话的开始：“ IF (秒差> 1200) 会话标记=1. EXECUTE.” 4）选取“ Andy发起的会话段数” 并生成新的变量：“ IF (发送者= 1) Andy=会话标记. EXECUTE.” 5）选取“ 好友发起的会话段数” 并生成新的变量：“ IF (发送者= 0) 好友=会话标记. EXECUTE.” 6）计算变量“ 单条会话时间” ：“ COMPUTE 单条会话时间=秒差. EXECUTE.” 7）将“ 单条会话时间” 限定在2 min以内：“ IF (单条会话时间> 120) 单条会话时间=120. EXECUTE.” 8）将一段会话的首条会话所花费的时间限定为2 min：“ IF (会话标记=1) 单条会话时间=120. EXECUTE.” 9）选取“ Andy的单条会话时间” 并生成新的变量：“ IF (发送者 = 1) Andy1=单条会话时间. EXECUTE.” 10）选取“ 好友的单条会话时间” 并生成新的变量：“ IF (发送者 = 0) 好友1=单条会话时间. EXECUTE.” 11）计算变量“ 响应时间” ：“ IF (发送者 = LAG(发送者)) 响应时间=发送时间 -LAG(发送时间). EXECUTE.” 。

2 样本分层聚类分析

2.1 样本处理摘要

机主Andy的78位好友中, 有50位好友“ Andy发起的会话段数” “ Andy未响应与已响应次数之比” 和“ Andy一般响应时间的均值” 中的一项或多项的值缺失, 本次样本分层聚类只选用其余28位好友数据进行分析。

2.2 样本分层聚类实验

2.2.1 操作步骤

在SPSS软件中依次点击：“ 分析” → “ 分类” → “ 系统聚类” , 进入“ 系统聚类分析” 对话框; 将“ Andy发起的会话段数” “ Andy未响应与已响应次数之比” 和“ Andy一般响应时间的均值” 选入“ 变量” 栏, 在“ 聚类” 中选择“ 个案” , 并输出“ 统计量” 和“ 图” ; 单击“ 统计量” 按钮, 在对话框中选择“ 合并进程表” “ 相似性矩阵” , “ 聚类成员” 里选择“ 方案范围：最小聚类数为2, 最大聚类数为10” ; 单击“ 绘制” 按钮, 在对话框中选择“ 树状图” , 在“ 冰柱” 栏中选择“ 所有聚类” ; 单击“ 方法” 按钮, 在对话框中选择“ Ward法” 聚类方法, 在度量标准中选择“ 平方Euclidean距离” , 在“ 标准化” 中选择“ Z得分” ; 单击“ 保存” 按钮; 返回主对话框, 在“ 标注个案” 中选择“ 好友名称” , 单击“ 确定” 。

2.2.2 命令分析

DATASET ACTIVATE 数据集1.

PROXIMITIES Andy发起的会话段数 Andy未响应与已响应次数之比 Andy一般响应时间的均值 /MATRIX OUT(‘ C:\Users\admin\AppData\Local\Temp\spss19776\spssclus.tmp’ )

/VIEW=CASE

/MEASURE=SEUCLID

/PRINT NONE

/ID=好友名称

/STANDARDIZE=VARIABLE Z.

CLUSTER

/MATRIX IN(‘ C:\Users\admin\AppData\Local\Temp\spss19776\spssclus.tmp’ )

/METHOD WARD

/ID=好友名称

/PRINT SCHEDULE CLUSTER(2, 10)

/PRINT DISTANCE

/PLOT DENDROGRAM VICICLE

/SAVE CLUSTER(2, 10).

ERASE FILE=’ C:\Users\admin\AppData\Local\Temp\spss19776\spssclus.tmp’ .

2.2.3 聚类结果

实验得到的近似矩阵表（如表1所示）说明, 近似矩阵中的数值越小, 表明二者距离越近; 数值越大, 表明二者距离越远。以“ Lucy” 为例, 距离“ Lucy” 最近的是“ Merry” , 距离“ Lucy” 最远的是“ F5” 。

表1 近似矩阵（节选） Table 1 Approximate matrix (excerpted)

实验得到的Ward联结聚类表（如表2所示）说明, 距离最近的个案最先聚合, 如“ 11” 与“ 23” , “ 27” 与“ 28” , “ 19” 与“ 20” , “ 13” 与“ 15” , “ 8” 与“ 14” , “ 9” 与“ 25” 等, 直到出现阶群集。

实验所得的群集成员表（如表3所示）说明, 当聚类数为“ 2” 时, 只有F5单独一组, 该样本在分类为“ 3” 、“ 4” 、“ 5” 等时都被单独分成一组, 据此可以判定该个案的特殊性。

实验所得Ward联结的树状图（如图1所示）说明, “ 类” 间的距离越大说明区别越明显, 如“ Merry” 和“ Lucy” , “ C1” 和“ G3” , “ Betty” 和“ Dave” 这三组个案因两两之间的相似性以及与其他分类的差异性而被独立出来。

结合近似矩阵、Ward联结聚类表、群集成员和树状图, 我们发现当聚类数分别为8、6、4的时候, 聚类效果最为明显。

表2 Ward联结聚类表 Table 2 Results from Ward-joint clustering

表3 群集成员 Table 3 Clustered Members

	Figure Option View Download New Window
	图1 会话段数与联系紧密度Fig.1 Session Segments and Relational Clossness

3 K-均值聚类分析

3.1 样本标准化

依旧选取机主Andy的28位“ Andy发起的会话段数” “ Andy未响应与已响应次数之比” 和“ Andy一般响应时间的均值” 三项数据不缺失的好友数据为实验数据。由于这三项数据的单位不一致, 在快速样本聚类之前, 需要先进行标准化处理。依次点击：“ 分析” → “ 描述统计” → “ 描述” , 进入“ 描述性” 对话框; 将“ Andy发起的会话段数（变量1）” “ Andy未响应与已响应次数之比（变量2）” 和“ Andy一般响应时间的均值（变量3）” 选入“ 变量” 栏, 在对话框下方选择“ 将标准化得分另存为变量” 。单击“ 确定” , 得到的标准化数据。

3.2 K-均值聚类实验

3.2.1 操作步骤

在SPSS软件中依次点击：“ 分析” → “ 分类” → “ K-均值聚类” , 进入“ K-均值聚类分析” 对话框; 将“ Andy发起的会话段数” “ Andy未响应与已响应次数之比” 和“ Andy一般响应时间的均值” 选入“ 变量” 栏, 在“ 聚类数” 中填入“ 6” , 在“ 方法” 中选择“ 迭代与分类” ; 单击“ 迭代” 按钮, 在对话框中填入“ 最大迭代次数为10, 收敛性标准为0” ; 单击“ 保存” 按钮, 在对话框中选择“ 聚类成员” ; 单击“ 选项” 按钮, 在“ 统计量” 中选择“ 初始聚类中心、ANOVA表、每个个案的聚类信息” , 在“ 缺失值” 中选择“ 按列表排除个案” ; 返回主对话框, 在“ 个案标记依据” 中选择“ 好友名称” , 单击“ 确定” 。

3.2.2 命令分析

QUICK CLUSTER Andy发起的会话段数 Andy未响应与已响应次数之比 Andy一般响应时间的均值

/MISSING=LISTWISE

/CRITERIA=CLUSTER(6) MXITER(10) CONVERGE(0)

/METHOD=KMEANS(NOUPDATE)

/SAVE CLUSTER

/PRINT ID(好友名称) INITIAL ANOVA CLUSTER DISTAN.

3.2.3 聚类结果

实验所得的最终聚类中心距离表（如表4所示）在一定程度上反映了各个类别之间的区分情况, 第1类与第3类的距离最大, 区分度最好; 第1类与第5类的距离最小, 区分度最差。类似地, 第3类与所有其他类别的区分度都非常好, 而第5类与除第3类外的所有其他类别的区分度都一般。

表4 最终聚类中心间的距离 Table 4 Distance among the final clustered centers

实验所得的方差分析表（如表5所示）说明, 本次参与聚类分析的三个变量中的任意一个变量的“ 类间均方” 都远远大于“ 类内的误差均方” 。从概率上看, 这三个变量使六个分类之间无差异的假设成立的概率都小于0.05%, 这说明该三个变量能够很好地区分各类, 聚类的效果是显著的。其中, “ 变量1” 对聚类的贡献最大, “ 变量3” 对聚类的贡献最小。

结合最终聚类中心间的距离、方差分析, 当聚类数预先设定为“ 6” 时, 聚类的整体效果最为明显。

表5 方差分析 Table 5 Analysis of variance

4 实验结果对比

将样本分层聚类结果整理成表6, K-均值聚类结果整理成表7, 通过对比分析得到如下结论：第一, 上述两种聚类方法得到的结果非常相似, 但在“ Dave” 的归属上, 样本分层聚类认为其是属于“ 不紧密且非常积极” 类, 而K-均值聚类认为其是属于“ 一般紧密且积极” ; 在“ C1” 的归属上, 系统聚类认为其是属于“ 不紧密且一般积极” , 而K-均值聚类认为其是属于“ 不紧密且非常积极” 。第二, “ Andy” 与微信好友的联系呈现出“ 扁平化” 结构。第三, 第一类和第六类的好友数量非常少, 而第三类和第四类的占比达到了57%。这说明“ 极好” 与“ 极差” 的好友是少量的, 大部分的好友都是处于“ 不紧密” 但“ 非常积极或积极” 的状态。从分类的效果以及聚类成员的分布来看, 这两种聚类的结果除个别样本外, 都相互得到了印证, 具有比较高的可靠性。

表6 样本分层聚类结果 Table 6 Results from clustering the layered samples

表7 快速样本聚类结果 Table 7 Results from K-means clustering

5 结果验证

选取上节中“ 一般紧密且积极” 的Lisa和Mike、“ 不紧密且非常积极” 的Betty和Fanny与Andy之间的会话段数累积和、一般响应时间进行数据分析, 将“ Andy发起的会话段数” 和“ 好友发起的会话段数” 的累积和用多线线图表现出来对比后发现“ 一般紧密” 的会话段数与“ 不紧密” 相比, 具有明显的连续递增的趋势, “ 一般紧密” 的累计和明显大于“ 不紧密” 的累计和, 如图2; 将“ Andy花费的一般响应时间” 和“ 好友花费的一般响应时间” 的值用多线线图表现出来对比后发现“ 积极” 的一般响应时间与“ 非常积极” 相比, 具有明显的波动性, “ 非常积极” 的一般响应时间的“ 值” 明显比“ 积极” 的一般响应时间的“ 值” 更集中, 如图3。

	Figure Option View Download New Window
	图2 会话段数与联系紧密度Fig.2 Session Segments and Relational closeness

	Figure Option View Download New Window
	图3 响应时间与联系倾向性Fig.3 Responding time and contact tendency

6 结论

本文通过对微信好友聊天数据时间特征进行研究, 设定了若干能反映“ 联系紧密度” 和“ 联系倾向性” 的变量, 然后对选定参与聚类的变量进行了样本分层聚类和K-均值聚类, 并对聚类结果进行了对比分析。经过分析和论证, 本文采用的以“ 发起的会话段数” 、“ 未响应与已响应次数之比” 和“ 一般响应时间的均值” 为变量对人物关系的“ 亲疏远近” 进行分类的方法能够反映客观的实际情况, 可以用于案件中人物关系分析。同时, 本文在实验中发现, 即使在同一个分类里面, 各个成员之间依然各有差异, 例如对“ 联系一般紧密” 及以上的个案进行“ 联系倾向性” 分析, 就会找到“ 熟悉的陌生人” , 即那些“ 活跃” 在我们身边, 却被我们“ 冷落” 的人。接下来, 本文将针对单变量对人物关系的影响、聚类过程中的异常值分析等展开深入研究, 以期获得更有价值的发现。

The authors have declared that no competing interests exist.

作者已声明无竞争性利益关系。

参考文献

文献选项

[1]	HAN J W, MICHELINE K, PEI J. Data mining: concepts and techniques[M]. 北京: 机械工业出版社, 2012: 1-2 [本文引用:1]
[2]	谷斌主. 数据仓库与数据挖掘实务[M]. 北京: 北京邮电大学出版社, 2014. [本文引用:1]
[3]	李涛. 数据挖掘的应用与实践: 大数据时代的案例分析[M]. 厦门: 厦门大学出版社, 2013. [本文引用:1]
[4]	张引, 陈敏, 廖小飞. 大数据应用的现状与展望[J]. 计算机研究与发展, 2013, 50(S2): 216-233. [本文引用:1]
[5]	朱索格, 胡访宇. 基于海量数据的链接预测方法研究[J]. 电子技术, 2014(3): 31-35. [本文引用:1]
[6]	伍星宇. 基于相似度的社区发现算法研究[D]. 武汉: 华中科技大学, 2012. [本文引用:1]
[7]	王玙, 高琳. 基于社交圈的在线社交网络朋友推荐算法[J]. 计算机学报, 2014, 37(4): 801-808. [本文引用:1]
[8]	马茜. 社会网络中的节点影响力度量和K-节点集的影响力最大化问题研究[D]. 济南: 山东大学, 2017. [本文引用:1]
[9]	张倩, 李海港. 基于知识表达的迁移学习方法及其应用[M]. 北京: 中国矿业大学出版社, 2015. [本文引用:1]
[10]	钱景怡, 张玉峰. 基于人际网络挖掘的企业竞争情报获取研究[J]. 图书情报知识, 2009(3): 90-93. [本文引用:1]
[11]	孙晓玲, 林鸿飞. 人际网络关系抽取和结构挖掘[J]. 微电子学与计算机, 2008(9): 233-236. [本文引用:1]
[12]	上官梦轩, 康艳荣等. 基于二维相关度的嫌疑人社交网络分析方法研究[J]. 刑事技术, 2017, 42(2): 93-97. [本文引用:1]

2012

0.0

... 数据的爆炸增长、广泛可用和巨大数量使得我们的时代成为真正的数据时代,急需功能强大的工具从海量数据中发现有价值的信息,并把这些数据转化成有组织的知识^[1] ...

2014

0.0

... 经过近几十年的发展和完善,数据挖掘技术已经日益成熟,其主要方法有关联规则挖掘、分类与预测、聚类分析、遗传算法、文本挖掘、Web挖掘等^[2] ...

2013

0.0

... 社交工具及应用作为新兴媒体的代表,其本身所携带的社交信息、交流信息以及社交用户产生的大量文本、图像、音频、视频等内容对于数据挖掘来说又是挑战^[3] ...

2013

0.0

... 现在流行的在线社交工具如推特、脸书、博客、微博、微信等通常都含有大量的链接数据和内容数据,其中链接数据主要为图形结构,表示两个实体之间的通信,而内容数据则包含有文本、图像以及其他网络多媒体数据^[4] ...

2014

0.0

朱索格, 胡访宇. 基于海量数据的链接预测方法研究[J]. 电子技术, 2014(3): 31-35.

... 目前,基于链接的分析主要致力于链接预测^[5]、社区发现^[6]、社交网络进化^[7]和社会影响分析^[8]等领域 ...

2012

0.0

伍星宇. 基于相似度的社区发现算法研究[D]. 武汉: 华中科技大学, 2012.

在许多真实的网络中都存在模块或社区。社区的检测是社会网络学习的重要的课题，对于我们了解社会网络的内部关系和结构，进而应用到与社会网络相关的很多领域都有重要的意义。传统的基于相似度的社区发现算法比如GN算法在计算的时候时间复杂度非常高，而基于相似度的社区发现算法的结果主要取决于相似度的选择，有些相似度选择可能使得结果更准确，但是针对规模较大的网络，时间也要是考虑的主要因素之一，所以可以根据网络的不同要求来选择相似度的不同度量方法。目前基于相似度的算法中有两个经典算法，分别是GN算法以及AP算法。GN算法中的时间复杂度非常高，针对这个弱点，可以提出一种基于扩散核特征矩阵相似度的分裂算法和一种基于DSD相似度的分裂算法。这两个算法都是基于网络拓扑结构的算法，避免了GN算法中的计算边介数的时间复杂度高的弱点。实验的结果表示，两个算法的划分效果和GN算法差不多，在效率上有很大的提高，对于相似度的度量方法的研究有一定的价值。 Newman贪婪算法是近期社区发现的一个主要算法，拥有准确快速的特点，但是当社区规模过大时，可能会使得社区规模分配不均。在比较基于扩散核特征矩阵的相似度和基于DSD相似度度量方法的优缺点之后，使用DSD相似度度量算法结合Newman贪婪算法(CNM算法)，既结合了CNM算法快速准确的优点，而且在一定程度上避免了CNM算法的社区规模分配不均匀的情况。

... 目前,基于链接的分析主要致力于链接预测^[5]、社区发现^[6]、社交网络进化^[7]和社会影响分析^[8]等领域 ...

2014

0.0

王玙, 高琳. 基于社交圈的在线社交网络朋友推荐算法[J]. 计算机学报, 2014, 37(4): 801-808.

为用户推荐朋友是在线社交网络的重要个性化服务.社交网站通过用户之间是否有相同属性信息或公共邻居判断他们能否成为朋友,但由于用户注册信息不完善和对公共邻居之间关系的忽略,推荐精度不高.事实上用户的朋友可以组成多个社交圈,拥有相似社交圈的用户更易成为朋友.因此,首先提出了社交圈检测算法,进而定义用户间的社交圈相似性,基于社交圈相似程度为用户推荐新朋友.使用YouTube数据验证了该文假设;使用Facebook自我网络数据,验证了社交圈检测方法的有效性,并与3种典型检测算法比较;使用区域Facebook数据,通过与公共邻居、Jaccard相似性比较,进一步验证了朋友推荐方法的准确性.

... 目前,基于链接的分析主要致力于链接预测^[5]、社区发现^[6]、社交网络进化^[7]和社会影响分析^[8]等领域 ...

2017

0.0

马茜. 社会网络中的节点影响力度量和K-节点集的影响力最大化问题研究[D]. 济南: 山东大学, 2017.

互联网技术的快速发展使得微博、微信等社会网络逐渐成为大众获取信息、分享信息的重要媒介。社会网络的出现使所有的网络用户都有机会参与到信息传播的过程中,用户不仅是信息的接收者,同时也是信息的发布者和传播者。用户的影响力在信息传播过程中发挥着巨大的作用,有影响力的用户能够推动信息的大规模扩散,快速地吸引更多的用户关注。因此,选择一定数量的有影响力的用户(被称为种子节点)在社会网络中进行口碑营销已成为一种重要的产品营销手段。除了在市场营销领域,识别和利用有影响力的用户在挖掘意见领袖、控制谣言传播、推荐等方面也有着巨大的应用价值。随着网络规模的不断扩大,如何衡量大规模社会网络中用户的影响力、如何选取一定数量的用户利用他们的影响力以实现信息的最大化传播(也被称为影响力最大化)等问题已成为目前国内外研究的热点,也是本文关注的主要问题。本文以国家自然科学基金为依托,围绕社会网络中的影响力传播这一研究主题,主要针对社会网络中的用户影响力度量和影响力最大化这两个关键问题展开研究。本文的主要工作和创新点包括以下几个方面。(1)本文提出了一种考虑传播概率的动态节点影响力度量方法。网络中节点的影响力可看作节点的传播能力,即以该节点为起始节点的传播过程最终在网络中覆盖的节点数量。传播概率是影响传播结果的重要因素,同一节点的传播能力在不同的传播概率下是不同的。传统的影响力度量方法没有考虑这一因素,导致这些度量方法对传播概率敏感,例如度中心性在传播概率较小时度量效果较好,而半局部中心性在传播概率较大时度量效果较好。为了减轻度量方法对传播概率的敏感性,本文利用度中心性和半局部中心性在不同传播概率下表现恰好相反的特点,将传播概率作为一个参数将这两者结合,提出了混合度中心性方法。本文的方法可自然地根据传播概率的变化调整度中心性和半局部中心性的比例以适应节点影响力在不同传播概率下的传播特点。实验结果表明,该方法在不同的传播概率下表现稳定,且在绝大多数传播概率下均能取得最优的度量效果。(2)本文提出了一种可调节的基于有限步传播的节点影响力度量方法。通过对比大量的实验,本文发现常见的节点影响力度量方法不仅对传播概率敏感,对网络结构也存在敏感性。面对一个未知的网络,无法确定哪种度量方法有效。针对这个问题本文提出一种强鲁棒性的度量方法——可调节的有限步传播方法。根据社会网络的传播特点,本文的方法基于传播路径计算了一个节点对其四步之内的节点的影响力。为了降低时间复杂度,我们将距离该节点二三四步远的节点看作一个整体,粗略估算了节点对这部分较远节点的影响力。通过设置并调节参数,该方法可以适应不同网络的传播特点。实验表明,我们的方法在不同类型、不同规模的网络中均有较好的表现,具有很强的鲁棒性,且方法中参数的选取有一定的规律可循,具有很好的实用性。(3)本文提出了一种适用于微博网络的影响力最大化算法。本文关注并致力于解决影响力最大化在微博网络中应用存在的两个问题:一是如何将微博中的行为、内容等信息应用到影响力最大化问题中,二是解决贪心算法及其改进算法在大规模社会网络中运行效率低的问题。本文利用微博网络中的行为、内容等信息对用户之间的影响力强度建模,并将其与传播模型相结合,增强了传播模型的实用性;针对贪心算法在大规模网络中运行效率低的问题,本文将节点影响力度量与影响力最大化问题相结合,提出了一种基于候选节点的影响力最大化算法。该算法首先对节点影响力进行简单评估,保留影响力较大的节点作为候选节点,再运用贪心算法从候选节点中选择种子节点。本文系统地分析比较了常见的节点影响力度量方法所选择的候选节点对种子节点选取结果的影响。实验表明,该方法可以大大缩短种子节点的选取时间,且不影响种子节点的选取效果。(4)本文提出了为未激活的种子节点寻找替补节点的问题及解决方法。当部分种子节点无法激活时,如何有效地寻找替补节点来代替它们以减少损失,这是影响力最大化在实际应用中很有可能遇到的问题。通过对问题的分析本文提出了三种寻找替补节点的策略:1.通过对影响力最大化问题中的静态贪心算法进行扩展,提出了有理论依据的扩展的静态贪心算法;2.为了提高贪心算法寻找替补节点的效率,本文利用静态图模拟传播过程的特点,提出了全静态算法;3.提出了在选择种子节点时多选一部分预备种子节点作替补节点的预选式贪心算法。实验结果表明:本文提出的三种方法选出的替补节点均能很好地代替未被激活的种子节点。

... 目前,基于链接的分析主要致力于链接预测^[5]、社区发现^[6]、社交网络进化^[7]和社会影响分析^[8]等领域 ...

2015

0.0

... 而基于内容的分析主要聚焦于关键字搜索、分类、聚类和异构网络中的迁移学习^[9]等方面 ...

2009

0.0

钱景怡, 张玉峰. 基于人际网络挖掘的企业竞争情报获取研究[J]. 图书情报知识, 2009(3): 90-93.

摘　要：本文将数据挖掘技术与人际网络相结合来实现企业竞争情报的采集。在分析企业人际网络结构及其特征的基础上，提出了企业人际网络的挖掘流程，以及如何识别企业人际网络内的重要节点类，并对节点的重要性进行评分的方法。进而，本文应用企业人际网络的挖掘方法，探讨企业竞争情报的聚类分析、关联分析、概念描述、预测等获取方法。

... 近年来,有学者不断提出了基于新方法的人物关系的定量分析,如基于聚类分析（依据距离和相关系数来评估不同样本在属性上的相似性）与关联分析（分为同类事件的简单关联和不同事件的次序关联）的方法获取人物关系等^[10],也有学者利用关系抽取技术,扩展传统的二元关系,提出了一种基于同义词词林的抽取关系描述词的方法,并通过该方法在收集一定量特定领域内的人物关系信息的条件下实现人际网络的定量分析及结果的可视化^[11],这在一定程度上促进了人物关系刻画技术的发展 ...

2008

0.0

孙晓玲, 林鸿飞. 人际网络关系抽取和结构挖掘[J]. 微电子学与计算机, 2008(9): 233-236.

社会是一个由多种多样的关系构成的巨大网络.对社会网络进行研究,可以揭示关系的结构,解释一定的社会现象.为此首先引入关系以及关系描述词的定义,利用关系抽取技术,扩展传统的二元关系,提出了一种基于同义词词林的提取关系描述词的方法,并收集特定领域内的人物关系信息构建成人际网络.接着对人际关系网络的拓扑结构,社区发现以及网络社区核心人物进行了研究,同时对分析结果实现了可视化.结果表明,社会网络分析可以揭示真实社会中的许多现象,有助于人们理解和开发这些网络.

2017

0.0

上官梦轩, 康艳荣等. 基于二维相关度的嫌疑人社交网络分析方法研究[J]. 刑事技术, 2017, 42(2): 93-97.

... 本文在前人及笔者之前的研究^[12]基础上,以微信聊天记录的时间信息为研究对象,首先对微信聊天记录数据进行预处理,包括文件格式转换、数据结构定义、计算变量选取,接着按照微信聊天形式将其抽象为会话段数、会话时长和响应时间三个要素并使用聚类算法对其进行量化研究,最后对使用不同算法得到的数据结果进行了对比分析,发现了会话段数与联系紧密度、响应时间与联系倾向性等关系,为案件侦查过程中快速寻找犯罪团伙、重点嫌疑对象提供了一种新的技术手段 ...