社交网络匹配算法研究与改进

发布时间：2020-03-27 06:43

【摘要】：使用多种多样的在线社交网络进行社交活动已经成为当前社交的特色。每个在线社交网络反映了我们真实社交网络的一个方面。将多个在线社交网络连接起来的社交网络匹配算法对于我们进行全面的社交网络分析具有重要作用。但是目前的在线社交网络匹配算法存在时间复杂度高、图间信息量较少的情况下匹配准确率不高、没有与其他领域知识很好的结合以提高实践应用能力等问题。论文对社交网络匹配算法的时间复杂度、匹配准确率和在实践中的应用进行了研究,提出了基于子图分割的社交网络匹配算法、基于有向图的社交网络匹配算法和基于多重社交网络匹配的好友推荐算法,并在实验上取得了很好的效果。主要研究成果如下:1.对于社交网络匹配算法的时间复杂度较高的问题,考虑到算法时间复杂度较高主要是因为算法中存在大量的冗余计算,我们可以通过分割成多个子图的方式把问题化整为零,并在分割的过程中引入社群分割算法,使得子图间的联系相对稀疏,子图内的联系相对紧密。基于子图分割的社交网络匹配算法通过分割子图后进行索引搜索的方式可以在社交网络图匹配的过程中节省匹配时间,节省了 30%时间。2.基于有向图的社交网络匹配算法有效的解决了有向图的匹配准确率不高问题,提出了基于方向的节点相似度计算方式,通过在计算网络层中两个点的节点相似度时引入方向性,有效的提高了匹配算法的准确性。在一些对方向性变化敏感的社交网络图间做社交网络图匹配时,算法准确率提升可达到10%。3.基于多重社交网络匹配的好友推荐算法很好的将传统好友推荐算法和社交网络匹配算法结合起来,提升了推荐的准确率。
【图文】：

社交,明星,统计特性,拓扑图

形式进行描述。通过用节点表示人，边表示人际交往关系，可将社交网络形式逡逑化描述为Ｇ＝｛Ｖ，Ｅ｝，其中Ｇ代表社交网络，，Ｖ代表点的集合，Ｅ代表边的集合（可逡逑以是有向边集或无向边集）［９］。图２－１选取了新浪微博网络的一部分节点和边逡逑对典型的在线社交网络结构进行示意。逡逑图２－１是从新浪微博人气排名（被关注数排名）前十的用户中选取八位用逡逑７逡逑

社交,网络匹配,算法模型,关系图

的最小值即为有效直径。图二（ｂ）中网络的直径为３，对应的最短路径为Ｇ－Ｅ－Ｆ－Ｈ逡逑或邋Ｇ－Ｅ－Ｆ－Ｄ。逡逑例２－１计算图２－１邋（ｂ）所示网络的平均路径长度与网络直径［１２］。逡逑解：首先计算出网络所有节点对间的距离：ｄｃｊＥ＝ｌ；邋ｄＧＢ＝２；邋ｄ0Ａ＝２；邋ｄＧｃ＝２；逡逑ｄＧＦ＝２；邋ｄＧＨ＝３；邋ｄＧＤ＝３；邋ｄＥＢ＝ｌ邋；邋ｄＥＡ＝ｌ邋；邋ｄＥＣ－１邋；邋ｄＥＦ＾ｌ邋；邋ｄＥＨ＝２；邋ｄＥＤ＝２；邋ｄＢＡ＝ｌ邋；逡逑ｄＢＥ＝ｌ邋；邋ｄＢＣ＝２；邋ｄＢＨ＝＝２；邋ｄＢＤ＝２；邋ｄＡＦ＝ｌ；邋ｄＡｃ＝２；邋ｄＡ0＝２；邋ｄＡＨ＝２；邋ｄｃＦ＝ｌ；邋ｄｃＨ＝２；逡逑ｄｃＤ＝２；邋ｄＦＨ＝ｌ；邋ｄＥＤ＝ｌ；邋ｄＤＨ＝ｌ。将以上数据代入式（２－２）可得逡逑Ｌ邋＝邋—－—Ｙｄａ＝１．６４逦（２－４）逡逑８（８－１）逡逑根据式（２－３）可求得直径逡逑Ｄ邋＝邋ｍａｘ邋ｄｕ邋＝邋ＤＧＨ邋＝邋Ｄｇｄ邋＝邋３逦（２－５）逡逑２．２在线社交网络一致性匹配算法逡逑在线社交网络一致性匹配问题是我们在进行跨社交网络间账户识别时最常逡逑遇到的问题，以往的很多一致性匹配算法大多数基于社交网络图中个人的行为逡逑特征来进行在线社交网络的一致性匹配。但是这种方式需要进行大量的个人行逡逑为分析［１３］。除此之外，在不同类型的社交网络中人们的行为特征可能出现较大逡逑差异。目前的社交网络一致性匹配算法从社交网络图的角度出发，利用社交网逡逑络图的特点进行图与图之间的匹配，而非单个账户的识别。这个问题类似于图逡逑的同构问题。但是图的同构问题是一个ＮＰ问题
【学位授予单位】：北京邮电大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP393.09

【参考文献】