社会网中三种类型种集发现算法研究

《社会网中三种类型种集发现算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Ｉ＼＠冷：硕：ｔ職生学位论文社会网中Ｈ种类型种集发现算法研究申请人：李智慧Ｉ学号：２１３１３２８培养单化计算机科学技术学院Ｔ学科专业：计算机科学与技术研巧；方向：化会网指导教师：李建中教授完成日期：２０１６年３月２７日独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研巧工作及取得的研充成果。据我所知，除了文中特别加标注和致谢的地方外，论文中不包含其他人己经发表或撰写过的研究成果，也不包含为获得黑龙江大学或其他教育机构的学位或证书而使用过的材料。－学位论文作者签名签字日期：年＾月＾日学

2、位论女版权使用授权书本人完全了解黒龙江大学有关保留、使用学位论文的规定，同意学校保留并。向国家有关部口或机构送交论文的复印件和电子版，允许论文被查阅和借阅本人授权墨龙汪去堂可１＾＾将学位论文的全部或部分内容编入有关数据库进行检索，可１＾采用影印、缩印或其他复制手段保存、汇编本学位论文。学位论文作者签名导师签名：．聋連中签字日期：心年＾月／日签字日期：心年作＾日学位论文作者毕业后去向：：电话工作单位：通讯地址：邮编：分类号UDC密级公开硕士研究生学位论文社会网中三种类型种集发现算法研究申请人:李智慧学号:2131328培

3、养单位:计算机科学技术学院学科专业:计算机科学与技术研究方向:社会网指导教师:李建中教授完成日期:2016年3月27日中文摘要在对社会网的研究中，影响传播问题的研究占有重要地位，一直是人们研究的重点问题。然而现有的大部分研究忽略了一个重要的事实，即地理位置信息对于社会网的影响传播问题是至关重要的，许多像位置敏感的口碑营销一类的真实应用都有地理位置的需求。为此，本文将地理位置因素引入到社会网中，分别研究了最小种集选取问题、利润最大化种集选取问题和影响事件组织者选取问题。本文的主要研究成果有：1.在传统的最小种集选取问题中引入地理位置因素，提出了位置敏感的社交网中最小种集选

4、取算法问题。对该问题进行了深入研究，发现该问题是NP-hard问题，并提出一种朴素的贪心算法MS-Greedy。MS-Greedy虽具有近似保证，但其计算量太大。为满足在线查询的需求，我们又提出了另外两种高效的算法Bound-based和Partition-Assembly-based。在大量真实数据上进行实验，实验结果表明：本文算法能够有效地解决位置敏感的J-MIN-Seed问题。2.在传统的利润最大化问题中引入地理位置因素，提出了位置敏感的社交网中利润最大化种集选取算法问题。在经典的IC模型中，融入价值和售价因素，提出了新的IC-V模型，并证明在该模型下研究的问题是

5、NP-hard问题。提出一种贪心算法Greedy，并在Greedy算法中融入三种制定售价的策略，提出求解位置敏感的社交网中利润最大化种集选取问题的三种算法。最后，在大量真实的数据上进行实验，验证三种算法的效率。3.在传统的影响事件组织者选取问题中引入地理位置因素，提出了位置敏感的社交网中影响事件组织者选取算法问题。首先举例说明该问题的重要性，形式化该问题，并证明其是NP-hard问题。其次，参考前人的工作，将已有的两种贪心算法用于求解该问题，由于贪心算法可能遗漏结果，我们提出了两种近似算法。最后，在大量真实数据上进行实验，对这四种算法进行比较，证明我们算法的有效性和高效

6、性。关键词影响最大化；社会网；最小种集选取；利润最大化；事件组织IAbstractInthestudyofsocialnetworks,thestudyofinfluencepropagationproblemoccupiesanimportantposition,andithasbeenthefocusoftheresearch.Butmostexistingworksneglectedthefactthatthelocationinformationcanplayanimportantroleininfluencepropagationproblemofsocial

7、networks.Manyreal-worldapplicationssuchaslocation-awareword-of-mouthmarketinghavelocation-awarerequirement.Therefore,thearticleintroducesgeographicallocationfactorintosocialnetworks,andrespectivelystudiesminimizingseedsetselectionproblem,profitmaximizationseedsetselection