面向目标市场的信息最大覆盖算法  

Maximize Information Coverage Algorithm for Target Market

作　　者：张伯雷 钱柱中[1] 王钦辉[1,2] 陆桑璐[1] 

机构地区：[1]南京大学计算机软件新技术国家重点实验室,南京210023 [2]南京陆军指挥学院军队管理系,南京210045

出　　处：《计算机学报》2014年第4期894-904,共11页Chinese Journal of Computers

基　　金：国家自然科学基金委创新研究群体科学基金(61321491);国家自然科学基金(61202113);国家自然科学基金重大集成项目基金(91218302);江苏省自然科学基金(BK2011510)资助~~

摘　　要：当一个企业或商家需要投放广告时,往往会先通过历史数据、个人兴趣等挖掘出可能购买自己产品的用户,即目标市场(Target Market),然后将广告信息通过电视、报纸等公共媒体的形式传递给这些目标用户,希望有更多的目标用户接受信息.然而调查显示,相比于传统大众媒体,人们更倾向于从自己认识的人那里去获取信息,因此文中考虑利用社会影响力的方式去传播广告:在社会网络中说服有限数目的初始用户,并让他们向熟识的人传播信息,期望信息可以通过级联传播覆盖尽可能多的目标用户.由于以往的信息覆盖最大化的工作集中于对全局网络的考虑,因此会忽略目标节点和全局网络之间的联系.通过数据观察可以发现,目标用户往往会由于同质性等原因而聚集在一起,因此文中提出基于聚类的KCC算法,算法通过对用户进行聚类分析,找出每个聚类的代表性用户,使得这些代表性节点可以影响尽可能多的目标用户,同时避免他们之间对信息覆盖的重叠.在不同的真实的数据集的实验显示KCC可以在大多数情况下取得优于其它常用算法的性能,尤其当种子节点数增多时,KCC可以更多地避免节点之间信息覆盖的重叠,从而取得更好的效果;同时,KCC只需要很短的运行时间,具有良好的可扩展性.When an enterprise or company delivers product advertisement into the market,itmight first analyze the purchase history and personal interests of users,and mine valuablecustomers who will potentially buy their products,which is denoted as target marketing.Comparedwith traditional mass media such as newspapers or TV,“word-of-mouth”diffusion in socialnetworks is considered to be more trustful for people.So we consider delivering advertisementwith social influence：by selecting a small set of people as seed nodes to spread information viasocial links,the information of advertisement is expected to cover as many target users as possible.Previous algorithms in influence maximization neglect the relationship between the globalnetwork and local target market,so they are not applicable in this problem.In this paper,wepropose KCC algorithm to select the seed nodes.KCC clusters the nodes and finds representativesin each cluster by defining the similarities and cost of the clusters.It also reduces the overlappingof the coverage of each representative.The algorithm is conducted on different real data sets andcompared with several other well-known algorithms.The results show that KCC performs better in most cases,especially when the seed set size grows larger.Moreover,it only needs a lowrunning time so is scalable for large networks.

关 键 词：社会网络 目标营销 信息传播 影响最大化 社会计算 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]