毕业论文-在线社会网络信息传播最大化算法实现.doc

河北经贸大学毕业论文河北经贸大学经济管理学院毕业论文在线社会网络信息传播最大化算法实现专业名称： 计算机科学与技术 班 级： 11级计算机1班 学生姓名： 指导老师： 完成时间： 2015年5月 34摘要近年互联网技术的迅速发展为社会网络的研究提供了大量的数据，同时移动客户端的大量普及也解决了大规模数据的处理问题,使社会网络信息传播效率越发重要。在商业中的“病毒式”营销中社会网络信息传播最大化至关重要，商业中追求付出最小营销成本的同时尽可能多的获得商业回报。通过社会网络信息传播最大化可以让商家付出最小的代价而使需要传播的信息在社会网络中传播最广泛。本文主要包含内容：(1)介绍在线社会网络信息传播最大化算法的发展现状，了解IC模型和LT模型的流程和具体作用，体会两种模型的区别；(2)实现三种影响力最大化算法，包括贪心算法，CGA算法，度中心算法。关键词 社会网络；病毒式营销；影响力最大化；贪心算法 。AbstractIn recent years, the rapid development of Internet technology to the research of social network provides a large amount of data, at the same time the mobile client popularity also can solve the problem of mass data processing, make social network information transmission efficiency is more important.The focus of this article is the maximization of the social network influence is mainly used in the viral marketing in business, this is the purpose of marketing in a minimum of marketing costs at the same time to get to the commercial returns as much as possible. Social network influence maximization research purpose is to find a most influential initial information collection makes the cost minimum and the most widely spread in the social network.In this paper, the research contents mainly include the following: (1) to introduce influence maximization algorithm development present situation, the influence of several main propagation model and to study the influence maximization algorithm, detailed introduction of IC model and LT model and discusses the advantages and disadvantages of each algorithm; (2) to realize the maximization of the influence of the main algorithms, including the greedy algorithm, and then, the degree of center algorithm and CELF algorithm and CGA algorithm, NEWGREEDY algorithm, MIXGREEDY algorithm, MAGA algorithm.Keywords：The social network Viral marketing Maximum impact Greedy algorithm 目录摘要IAbstractII1 引 言11.1 研究背景与意义11.2 研究目标与内容22相关理论知识42.1 社会网络42.2 影响力最大化问题52.3 影晌力传播模型62.3.1 独立级联模型62.3.2 线性阈值模型62.4 典型的影响力最大化算法82.4.1 贪心算法82.4.2 CGA算法82.4.3 度中心算法93算法的实现流程103.1 IC模型的程序流程103.2 LT模型的程序流程123.3 贪心算法流程133.4 算法设计流程144算法实现164.1 贪心算法164.2 CGA算法184.3 度中心算法195实验215.1 实验环境215.2 实验平台215.3 真实数据216结论226.1 论文总结22致谢23参考文献241 引 言1.1 研究背景与意义个体及个体之间的复杂关系组成了一个复杂的网络，那就是是社会网络。从19世纪20年代早期开始，为了研究社会个体之间的关系，从关系中找出有实用价值的规律，社会网络的相关研究应运而生。这门学科对控制有效的信息的传播和扩散有重大的作用。当推销一种产品时，先推销给一个人，这个人会对他的亲友和同事推荐，可能其中有部分人会接受他的推荐，并进一步向他们自己的亲友或同事推荐，这个级级推荐的过程称为传播。个人的行为在很大程度上取决于周边的朋友或同事的决定。经过长时间的研究，最终将影响最大化问题归纳为算法上的问题，就是如何选取网络中最有影响力的个体，提供给这些个体免费的样品，再通过这些个体推荐给其他的网络中的成员，从而达到最快速传播的目的。研究网络信息传播最大化有十分重要的实际意义，这个课题在广告传播，产品市场营销以及社会安定等方面十分重要。随着微信，移动的快速发展流行，目前出现了很多大型在线社交网站。这些大型在线社会网络的成员数目庞大，对社会的传统营销模式产生了新的挑战。如何让社会网络信息传播的速率最大成为研究热点。目前，在市场中常见的营销方式有直销和大众营销两种，但此两种营销方式都忽略了人与人之间存在的客观联系。其中大众营销是指商家在市场中投入大量广告或者在卖场不段举办产品促销来寻找新的客户，大众营销需要花费巨大的费用。直销比大众营销效率高些，是利用市场调查或数据挖掘等数据搜集手段寻找最有可能购买产品的用户，然后有针对性的向这些用户推销产品。以上两种营销方式都没有考虑了人和人之间存在的相关联系，所以这两种方式未必有理想的效果，所以营销模式中出现了一种新的方式叫“病毒式营销”。其营销原理是：商家在推出一种新型产品时，拿出一部分产品免费送给一部分人试用，这部分人试用产品然后再将这种产品推荐给他们周围亲近的人，而这些人又把这种产品推荐给他们自己的朋友，从而产生“口碑效应”，产生了级联推荐的效果。而朋友之间的关系一般是可信任的，这就使传播速率大大增加。商家们所考虑的是怎样利用有限的资金找到这些可以最大加强传播效率的初始个体从而使产品的影响力达到最大化。此种营销方式尽可能的利用了网络个体之间的相互关系来达到最好的营销结果，可以用最小的资金得到更多的回报。目前随着国内的人人网、新浪微博、开心网、腾讯微博等社交网络的迅速发展，利用社交网络来进行产品的营销也迅速进入商家们的眼球。目前在社交网络上进行产品的网络营销是比较火的，例如最新兴起的微商。但如何选取影响力比较大的用户来推广产品，最终使产品的传播达到最大化是考虑的首要问题。也就是传播的最大化。信息是时刻在传播的，我们需要考虑如何控制信息传播的速度，如何选择最有影响力的个体来加速商品信息的传播速度，从而使产品的推广信息的影响力达到最高。同时社会信息网络中也有谣言这些不良信息的传播，实际上他们都是某种符合特定规律的传播行为，通过找出不良信息的传播源头和其中影响力最大的传播种子可以将这些传播种子除掉从而扼制这种快速传播。所以通过研究社会信息网络传播的最大化可以有效控制信息的传播。1.2 研究目标与内容社会信息网络传播的最大化越来越重要，所以出现很多的相关算法来计算如何加强传播速率。本文初步了解社会信息网络传播的最大化，安排如下：(1)了解社会信息网络传播的最大化的意义和研究现状。(2)学习了相关的理论知识，了解独立级联模型和线性阈值模型这两种传播模型的流程。(3)重点学习了贪心算法、CGA算法，NEWGREEDY算法，并详细了解这些算法的实现原理。(4)实现以上的算法，体会通过算法实现最大化传播的原理。(5)进行实验，通过导入有效的数据集，通过分析验证了算法的有效作用。2相关理论知识2.1 社会网络从1736年就开始了社会网络传播的研究。网络实际上是一种图形结构，事物之间的某种特定关系构成了网络。而社会网络与上述“网络”的定义相似，是由多个个体和其他个体的连线组成的集合。社会网络中的个体可以是不同的社会成员，也可以是集体性的社会单位。而社会成员之间的关系是多种多样的，可以是个体之间的合作关系，互动关系，朋友关系，上下关系。社会网络关注的是个体之间的互动和联系，个体间的互动影响着个体的社会行为。社会网络中著名的理论是150法则和六度分割理论。150法则是一个人可以保持社交关系最大的人数，个体通过任意社会性网络服务与其他个体建立了弱链接在此时此刻符合150法则。六度分割理论是说最多通过六个人你就能够认识任何一个陌生人。这说明了社会网络中普遍存在着“弱纽带”，这使得人与人之间的距离变得非常相近。社会网络是相对稳定的。不同的社会网络内部，可能是紧密联系的，也可能是松散联系的，但一般而言，社会网络一旦形成，就具有相对的稳定性。社会网络也是一个图结构，图结构中的每个节点表示一个个体，边可以表示个体之间的关系。如2.1图所示，图中的节点表示不同的人，边表示人之间的人际关系，由此形成的一个社会网络。而图中又体现出不同人群之间的联系，由此可以看出同群体内的关系比较频繁，不同群体之间的人也存在人际关系但关系比较少。图2.1 社会网络图2.2 影响力最大化问题社会信息网络传播的最大化要解决的问题是如何利用有限的资金来寻找初始的个体，由初始的个体去影响网络上的其他个体，使最终被影响的节点数目达到最大。这个问题首次由Domingos和Richardson提出的，其提出的理念可以概括为：给定一种特定的影响力传播模型和一个社会网络图，给定初始的节点个数，在网络上确定初始的节点集合，集合中的节点是被激活的，从这些集合中的节点开始传播，使最终被影响的节点数目达到最多,其符号化的表式如下：给定一个社会网络G=，V为节点集合，E为边的集合，如何从网络G中选择k个初始的节点集合A，满足，按照某种传播策略，由这k个初始的节点开始影响其他节点，并使最终被影响的节点数目达到最大，公式化如下：其中集合A最终影响的节点数目为(A)。社会网络信息传播的最大化的指标可以归纳为以下两点：1)效率：如何用最短的时间找到k个初始的节点。2)效果：最终被这k个初始的节点影响的节点数目。2.3 影晌力传播模型社会网络信息传播的最大化问题的学习要基于网络传播模型，目前在社会网络信息传播的最大化研究中最常用的两种传播模型是IC和LT模型。2.3.1 独立级联模型算法的具体描述如下：1对于网络Gr，所有节点只有未激活和激活两种状态，所有节点不能有其他的转变方式，只能由未激活状态变成激活状态。2某一时间t，某一节点v，变成激活状态，此时v节点对其指向的未激活状态的节点m有变成激活状态的可能。节点v对节点m影响成功的概率是p(v，m)，如果节点m周围有多个已被激活的邻居节点集N(v)，则他们对节点m的影响顺序是随几的。由概率p(v，m)大小决定相关节点间的影响是否成功，这个概率越大，相互影响成功性越大。3节点m可能失败，也可能成功激活。如果节点m被成功激活，则它对它指向的节点就具有影响力。4对每个节点以上步骤，直到没有可被激活的节点为止，算法终止。实际情况中节点激活的概率可能不一样，为了便于管理，在实验中将同一个概率统一设定成激活概率。IC传播模型的关键点是用概率表示某个节点对其他节点的激活情况，这个概率越大表示其他节点激活的成功性越大。在实验中随机的生成一个O，l之间的概率值，将激活概率值和这个概率值对比，如果这个概率值比激活的概率值大，则节点被成功激活。2.3.2 线性阈值模型算法的具体描述如下：1对于网络Gr，所有节点只有未激活和激活两种状态，所有节点不能有其他的转变方式，只能由未激活状态变成激活状态。2用一个阈值v，来体现某个节点受影响的难易程度。这个阈值越大，则这个节点越难受其他节点的影响，反之阈值越小则这个节点越容易难被其他节点影响。对其有影响的邻居节点集合为A，对于任意wA，定义bw。为节点w对节点v的影响程度，影响程度用一个概率表示，而且满足3如果其他周围节点对节点v的累积影响力之和为，则节点v就会自动由未激活的初始状态变为激活状态。4节点v变为激活状态后又会对其它自己所指向的节点产生影响，以上过程不断循环，直到没有可激活的节点为止。LT模型传播机制的重要点是把激活某个节点的难易程度用阈值表示，当阈值越大时，当前网络中的这个节点越难被激活。只有当此节点的周围关系密切的节点对该节点的成功激活概率之和超过阈值时，该节点才会被激活。在实验中随机生成节点的周围关系节点对实验节点的成功激活概率，然后将所有已经被激活的周围关系节点对实验节点的激活概率求和，如果这个值超过阈值，则表示该节点被成功激活。在社会网络上寻找可以让影响力最大的节点需要借助于相关的传播模型，本文使用IC模型和LT模型作为实验的传播模型，将IC和LT传播模型封装为方法：l读取社会网路数据，构建社会网络G(V，E)，V为节点集合，E为节点之间有关联的边。无向网络可以看成相互指向的有向网络。2对于G中的任何一个节点y，根据特定的公式得出指向y的所有周围关系节点N(y)对y节点影响力的概率，这个概率就是IC模型中的概率p(v，m)和LT模型中6(v，m)，它描述节点y的周围关系节点m对y的影响力。3对G的每个节点都给出概率值，调用IC和LT模型后，为了得到当前节点对剩下节点的影响力，要通过实验来获得最终的传播结果图，这个特定图就代表所有节点之间的相互影响情况。实验网络在传播实验结束后得到所有节点间的成功的传播影响图，在传播图中某个节点若能够的成功影响另外一个节点则当前一对节点之间将形成有向边，可以借助这个传播结果图统计某个节点的影响力。2.4 典型的影响力最大化算法2.4.1 贪心算法贪心算法求解影响力最大化问题，计算初始的激活节点个数使影响力达到最大的公式如下：算法的核心思想：定义M为固定的传播测试次数，通过M次的测试传播得到M张测试传播图，将空集设定为开始时刻的激活节点集合。对于给定的开始时刻的任何节点v，在每张测试结果图Gr上计算其所有的节点集合F(v，Gr)，然后将|F（v，Gr）|累加再除以测试次数M得到单一节点的平均影响力，将平均影响力最大的节点加入集合A中，这是第一个激活节点。然后继续下一个激活的节点查找。将每个节点加入到A中，并计算AUv的后继集合F(AUv，Gr)，累加|F（AUv，Gr）|后求平均值，从平均值中得到第二个平均影响力最大的节点，将其加入初始的节点集A中。重复以上的步骤，直到|A|=k为止。算法终止，这样就可以得到初始的k个平均影响力最大的激活节点。使用贪心算法解决传播影响力最大化思想结构简单，易于理解，贪心算法最大的优点是可以获得相对稳定的解，算法的结果能保证获得最优解的63。但是它也有严重的缺点，就是时间复杂度非常高，对于一般上百个节点的网络，都需要很长的时间来完成初始节点的搜索工作，所以对于上千上万以上的大型网络贪心算法不适合，贪心算法适合于小型网络。2.4.2 CGA算法CGA算法是根据将网络分成各个独立的社区，先将初始激活节点个数最佳的分配到各个社区，最后将各个社区的影响力值求和得到最佳的影响力值。CGA算法使用贪心算法寻找初始各个社区的影响力节点。由于贪心算法的时间复杂度很高，因此CGA算法的时间复杂度也高很多。因为CGA算法将传播网络划分成了单一的小型的网络，因此它相比贪心算法的时间复杂度有很大数量级的降低。但是CGA算法使用贪心算法作为区域的寻找算法，时间复杂度依然比较高，而且由于传播网络分成各个独立区域之后会导致边的减少而影响传播。2.4.3 度中心算法度中心性测量网络中单一节点与其它的所有的节点相联系的程度，可以用无向图来表示。对于一个拥有g个节点的无向图，节点i的度中心性可以写作i与其它g-1个节点的直接联系总数，表示如下：其中CD（Ni）表示节点i的度中心度，用于计算节点i与其它g-1个j节点（ij，排除i与自身的联系；也就是说，主对角线的值可以忽略）之间的直接联系的数量。CD（Ni）的计算就是简单地将节点i在网络矩阵中对应的行或列所在的单元格值加总。如此测量的节点度中心性，不仅反映了每个节点与其它节点的关联性，而且也视网络规模（g）而定。也就是说，网络规模越大，度中心性的最大可能值就越高。为了抵消网络规模变化对度中心性的测试影响，凯瑟琳福斯特和斯坦利沃瑟曼提出了标准化的测量公式：在这个标准化度中心性测量公式中，用节点i的度中心性值除以其它g-1个节点的最大可能连接数，从而得到与节点i有直接联系的网络节点的比例。这个比例范围从0.0到1.0，0.0表示与任何节点都没有联系，1.0表示与每一个节点都有直接联系。在社会传播网络中，标准化的个体的度中心性测量个体在诸多关系中的参与程度是不同的。得到高分的个体是网络中最显眼的参与者。如果标准化度中心性值越接近1，那么此个体在传播网络中的参与度越高。3算法的实现流程3.1 IC模型的程序流程IC模型流程如图3.1所示：图3.1 IC模型程序流程图3.2 LT模型的程序流程LT模型流程如图3.2所示：图3.2 LT模型程序流程图3.3 贪心算法流程贪心算法运作流程如图3.1所示：图3.1 贪心算法流程图此传播图Gr中集合丁可达的节点集合F(T，Gr)，针对每个节点的可达性分析可以O (m)内完成，其中m为边数。此外算法还有三层for循环，时间复杂度为O(kMn)因此整个算法的时间复杂度为O(kMnm)，其中k为给定的初始激活节点个数，m为网络边的数量，n为网络的节点个数，M为给定的模拟传播次数。3.4 算法设计流程影响力最大化算法设计的的基本流程图如图3.4所示。图3.4 算法设计流程图测试时要读取社会网络数据集，将传播网络中的节点和边及其其他属性值保存起来，如果数据正确则可以调用构建和模拟传播模型，最后利用算法来寻找影响力最大的节点并计算最终的影响力值。在算法的设计实现过程中，本实验采用了Graph类来构造数据容器，在存储底层的数据结构上采用了STL的vector容器、SET容器和map容器来存储网络数据,Graph类的类图如图3.5所示：图3.5 类图4算法实现4.1 贪心算法/ main.cpp/ 111/ Created by tarena on 15/4/23./ Copyright (c) 2015年 tarena. All rights reserved.#include using namespace std; #define N 11 /一个活动用一个结点表示 struct node int id; int start; int finish; AN+1; /递归计算，贪心策略在第i个活动执行之后结束，初始时i=0 void Reccursive_Activity_Selector(int i, int n) int m = i+1; while(m = n & Am.start Ai.finish) m+; /若找到了 if(m = n) /将这个活动作为执行活动 coutm ; /递归第m个活动执行结束之后的贪心策略 return Reccursive_Activity_Selector(m, n); coutendl; return; /迭代的贪心算法 void Greedy_Activity_Selector() /在第i个活动执行结束之后的贪心策略，初始时i=0 int n = N, i = 0, m; for(m = 1; m = Ai.finish) /将这个活动作为执行活动 coutAm.id ; /递归第m个活动执行结束之后的贪心策略 i = m; coutendl; /* 0 0 /虚构活动a0 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14 */ int main() int i; /输入测试数据 for(i = 0; i Ai.startAi.finish; Reccursive_Activity_Selector(0, N); Greedy_Activity_Selector(); return 0; 4.2 CGA算法Initialize probability vector L is the number of bits in the genome for i:=1 to L do pi:=0.5 Generate two individuals from the vector a:=generate(p); b:=generate(p); Let them compete winner,loser:=evaluate(a,b); Update the probability vector toward the better one. N is the number of individuals in the simulated population. for i:=1 to L do if winneriloseri then if winneri= =1 then pi+=1/N else pi- =1/N Check if the probability vector has converged for i:=1 to L do if pi0 and pi1 then goto step2 Prepresents the final solution. 4.3 度中心算法A=load(C:UsersAdministratorDesktopcdbBA_4000_5_0_.txt);/数据/结构好像是每2个一组，例如3 4表示一组，表示点3和节点4有连/接。TT=A/取邻接表所有行，第一列到第二列，所有数加1，相当于消除/结点影响mixedsig=zeros(max(max(TT);/先让邻接矩阵归零 大小为maxtt*maxttlen=length(TT);for i=1:len mixedsig(TT(i,1),TT(i,2)=1;/有数就转化为矩阵中的1 mixedsig(TT(i,2),TT(i,1)=1;/因为是无向图，所以有（i,j），必定/有(j,i)enddisp(已转化为邻接矩阵！)ii = 1;degree = 0;/用于临时存放结点的度数%degreeStandardization = 0;degreeArray = 10000; /暂存这一轮所有节点的度数maxDegree = 100; /存放最大度结点位置degreeStandardization = 0; /标准化后的度数matrix=0,1,1,0,0;1,0,1,0,0;1,1,0,1,0;0,0,1,0,1;0,0,0,1,0;/第一步，创建一个矩阵matrix = mixedsig;len = length(matrix);for t=1:100 %总共选100个节点出来 for i=1:len degree = sum(matrix(i,:);/第i个节点的度数 degreeStandardization = degree/(len-1); /对节点度数进行标准/化处理 degreeArray(1,i) = degreeStandardization; end x, y = max(degreeArray); /x存放最大度数，y存放最大度数所在/位置 maxDegree(1,ii) = y; /将最大位置y存入maxDegree matrix(y,:) = 0; /让i结点成为孤立节点 matrix(:,y) = 0; degreeArray = 0; disp(maxDegree)end5实验5.1 实验环境l、硬件平台：一台戴尔品牌电脑2、操作系统：Windows 7，Service Pack 23、软件工具：vc5.2 实验平台在平台中可以设定传播网络是否带权、是否有向，可以设定影响力最大化算法中出现的参数，可以选择传播模型如线性阈值模型和独立级联模型，可以设定初始的影响力最大的节点个数或模拟传播次数和输入、输出文件的路径，这些参数设定后点击确定就可以进行影响力最大化算法的实验。5.3 真实数据1.Basketball数据集Basketball数据集是一种关系数据，网络中的每个节点代表一个球队，边代表球队之间的联系，网络的统计数据如图5.3所示：图5.3 统计数据图实验的参数设定如下：分别选取LT模型和IC模型为传播模型，试验次数为90次，初始的影响力节点个数为15、20、25、30、35，纵坐标为最终被影响的节点个数，横坐标X为初始的节点个数。6结论6.1 论文总结本文的主要工作是分析了目前一些影响力最大化算法，并在真实数据上对贪心算法和其他的算法进行了实现。本文的具体工作总结如下：1.在相关知识方面，本文介绍了社会网络的相关知识，包括社会网络的概念、特点、性质等；了解了信息如何在网络中快速传播，学习了相关的影响力最大化算法。2、本文重点研究了影响力最大化问题和传播模型的相关内容：首先介绍了影响力最大化问题的研究背景和意义；重点学习了重要的两种传播模型LT模型和IC模型，对这两种传播模型进行了详细描述和说明。3、本文研究了目前的一些影响力最大化算法，理解这些算法内在运行过程。各算法在真实数据上进行实验，得出的结论如下：1随着选择初始节点的个数增加时，贪心算法的时间复杂度也随着增加。贪心算法根本不适于在中大型网络上求解影响力最大化问题。2、在LT模型和IC模型中，度中心算法的实验效果比贪心算法、CGA算法都要好。3、影响力最大化算法的效果都随着给定的初始节点个数的增加而提高的。另外在IC模型，当传播概率增加时，求解影响力最大化问题的算法的时间复杂度也增加，算法的效果也有提高。致谢我在整个毕业设计期间有很大收获，也发现了自己的短处。今后，我一定更加努力学习，弥补自己的短处，提高自己的技术水平。在本次毕业设计中，刘老师严谨的治学精神，认真负责的指导态度，使我受益匪浅。无论在理论上还是在实践中，都给予了我很大的帮助，让我得到了很大的提高，这对于我以后的工作和学习有巨大的帮助，非常感谢老师的耐心指导。我还要感谢我的大学生活，大学里的每一个老师，同学，朋友。是他们在一直支持我，让我的大学生活丰富多彩，你们是我永远的回忆与牵绊。感谢河北经贸大学经济管理学院对我的培养，让我从懵懂的无知少年有了一技之长，去迎接社会的考验。我会努力，为母校争光。参考文献1 汪小帆，李翔，陈关荣复杂网络理论及其应用，清华大学出版社20062周春光，卢廷玉，重叠社区结构的挖掘算法，吉林大学学报20093 Schelling T C Micromotives and Macrobehavior M New York: Norton，19784 杨学瑜，高立军，软件开发过程与项目管理，电子工业出版社，2008.5 林聚任社会网络分析：理论、方法与应用北京师范大学出版社，20096郑振杰.C+程序设计 北京：人民邮电出版社,20057柴欣，C/C+程序设计 河北大学出版社，20028余苏宁、王明福，C+程序设计 北京：高等教育出版社，20039 吕凤翥.C+语言程序设计（第2版）.电子工业出版社,2007.210 李云清、杨庆红、揭安全.数据结构M.人民邮电大学出版社,2004.611.M.Richardson and P.Domingos.Mining knowledge-sharing sites for viral maketing.In KDD,pages 61-70,2002. 12陈清华等。Visual C+课程设计案例精选与编程指导。东南大学出版社200413严华峰等.VISUAL C+课程设计案例精编(第二版).中国水利水电出版200414魏亮, 李春葆编著.Visual C+程序设计例学与实践.清华大学出版社.200615汪晓华等VISUAL C+网络通信协议分析与应用实现 人民邮电出版社 200416龙马工作室.VISUAL C+管理信息系统完整项目实例剖析.人民邮电出版2004河北经贸大学本科毕业论文（设计）开题报告申请书姓名： 叶云鹏 专业：网络工程 所属学院：信息技术学院 指导教师姓名： 刘院英 职 称： 讲师 开 题 报 告 时 间：2014年 10 月 8 日1、 拟选课题国内、外的研究动态、水平、存在问题，与本人实习、社会实践、调研的关系，并附主要参考文献：本文研究的重点是社会网络影响力最大化,该研究主要应用于商业中的“病毒式”营销,这种营销方式的目的是在付出最小营销成本的同时获取到尽可能多的商业回报。社会网络影响力最大化研究的目的是要寻找有k个节点的初始集合使得信息在该社会网络中传播最广泛。国内外现状：从论文中摘抄一些有关这些算法的内容参考文献：参考文献要有序号1 汪小帆，李翔，陈关荣复杂网络理论及其应用，清华大学出版社20062周春光，卢廷玉，重叠社区结构的挖掘算法，吉林大学学报20093 Schelling T C Micromotives and Macrobehavior M New York: Norton，19784 杨学瑜，高立军，软件开发过程与项目管理，电子工业出版社，2008.5 林聚任社会网络分析：理论、方法与应用北京师范大学出版社，20096郑振杰.C+程序设计 北京：人民邮电出版社,20057柴欣，C/C+程序设计 河北大学出版社，20028余苏宁、王明福，C+程序设计 北京：高等教育出版社，20039 吕凤翥.C+语言程序设计（第2版）.电子工业出版社,2007.210 李云清、杨庆红、揭安全.数据结构M.人民邮电大学出版社,2004.611.M.Richardson and P.Domingos.Mining knowledge-sharing sites for viral maketing.In KDD,pages 61-70,2002.12陈清华等。Visual C+课程设计案例精选与编程指导。东南大学出版社200413严华峰等.VISUAL C+课程设计案例精编(第二版).中国水利水电出版200414魏亮, 李春葆编著.Visual C+程序设计例学与实践.清华大学出版社.200615汪晓华等VISUAL C+网络通信协议分析与应用实现 人民邮电出版社 200416龙马工作室.VISUAL C+管理信息系统完整项目实例剖析.人民邮电出版20042、 课题拟解决的主要问题，在理论和应用方面的意义，完成课题的条件(包括实习单位情况)和论文（设计）的主要内容：解决的主要问题：了解网络传播原理，理解影响力最大化的原理，通过LT和IC模型测试，编写贪心算法，CGA算法，度中心算法。理解算法的内在原理，熟悉通过算法运行后的影响力传播过程。意义：了解在线社会网络信息传播最大化的原理，对相关体系知识有了自我的认识。3、指导教师对学生选题报告的评语： 指导教师签字： 年 月 日4、选题报告会评议组意见： 组长（签字）： 年 月 日5、学院审查意见： 主管院长（签字）： 学院（公章） 年 月 日河北经贸大学经济管理学院毕业设计开题报告毕业设计题目 在线社会网络信息传播最大化算法实现学生姓名 叶云鹏指导老师姓名刘院英 指导老师职称讲师 毕业设计内容：(1)实现IC模型和LT模型（2）实现主要的影响力最大化算法，包括贪心算法、度中心算法、CGA算法国内外现状、拟采用的方法及技术路线：国内外现状：从论文中摘抄一些有关这些算法的内容系统实现方法：1操作系