基于微博影响力的评价模型(最终版).doc

基于微博影响力的评价模型摘要本文研究的是微博用户和微博的影响力，以及最大好友圈和消息最佳发布问题。对于问题一，首先，我们查阅相关文献，基于已给数据将用户粉丝数量，用户和粉丝的活跃度，粉丝的专注度作为我们评价微博用户影响力的指标。根据这 些指标，我们对题目所给表格中的数据进行统计，将得到的结果作为各个用户在各指标下得到的分数。然后，我们建立了熵权模型，将这些数据进行标准化处理，对各个指标的权重进行了计算，分别得到了在不同人数的微博环境下各指标在评价用户影响力时所占权重。最后，将各指标下分数与权重相乘，再将各个用户的所有指标分数求和得到最终用户影响力评分。将其排序筛选后，得到影响力最大的十个大V编号。对于问题二，首先，在问题一所建立模型的基础上，我们确立了将微博被转发次数和转发人的影响力作为我们评价微博影响力的指标。然后，我们统计了各条微博在各指标下的数据。其次，我们利用熵权模型将数据标准化处理，并求出了这两个指标在评价微博影响力时所占权重。最后，我们将各微博各指标下分数与权重相乘，并将所有指标分数求和得到最终微博影响力评分。将其排序筛选后，得到影响力最大的十条微博消息。对于问题三，首先，我们根据题目对于好友圈的定义，将M=(i，j)定义为关注情况矩阵，即第j用户关注第i用户的情况。进而将多人相互关注的关系用函数关系式表达出来，将所有符合条件的用户编号写入矩阵中。然后，先通过对符合两两关注情况的用户进行筛选，再从筛选好的用户中逐步添加用户，判断是否为三人相互关注，四人相互关注，直至好友圈内不能再添加人为止。此时的 好友圈为最大好友圈。最后，我们通过循环算法实现上述过程，得到了2000人微博环境下10人为最大好友圈，10000人微博环境下13人为最大好友圈，并求出了好友圈中所有用户的编号。对于问题四，我们将其转化为优化问题，建立了0-1规划模型处理。首先，将用户发布消息与微博用户之间相互关注的情形转化为0-1矩阵（0表示用户未发布消息或表示微博用户之间未相互关注，1则反之），分别表示为x和A。这样若某用户能看到消息，则x与A转置后的矩阵乘积大于等于1。然后，我们将其推广至所有用户，将该问题转化为目标函数为发布消息的人数最少，约束条件为x与A转置后的乘积全部大于等于1的优化问题。最后，我们通过matlab中自带的遗传算法求得最小用户数。但发现效果并非很好。又采用了贪婪算法，求得了2000人微博环境下发布该消息的用户数最少为93人，10000人微博环境下则为249人。 本文建立的模型在已有文献的基础上有一定的改进，求解算法科学，定位速度更快，定位精度更高，有一定的实用和推广价值。关键词：微博影响力 熵权模型 遗传算法 贪婪算法1 问题重述1.1 问题背景微博，作为互联网上新兴应用，由于智能手机的普及，使得其运用变得极其方便，从而吸引了大量的注意力。而微博上的大V用户往往有着很大的影响力，如何正确而有效的评价用户影响力是需要关注的应用问题之一。1.2数据集数据文件data1.xls和data2.xls分别包含了当用户总量为2000和10000时这些用户的相互关注数据，每一行为该行号对应的用户对其它用户的关注信息。数据文件data3.xls和data4.xls分别为当用户总量为2000和10000时这些用户发布或转发的消息数据，每一行为该行号对应的用户发布或转发的消息编号。1.3 提出问题根据上述问题背景及数据，题目要求我们建立数学模型讨论下列问题。(1) 对具有较大影响力的大V定义合适的影响因子，并且找出影响力最大的十个大V。(2) 某些微博消息，被大量的用户关注和转发，因而具有很大的影响，请找出影响力最大的十条消息。(3) 在微博中，相互关注的用户被称为好友，对于一个群体，如果他们相互之间均为好友，则称为好友圈，请找出人数最多的好友圈。(4) 假设一微博用户发布的消息，其粉丝都会看到，如果要发布一则消息，确保所有用户都能看到（不考虑转发），请选择一种发布该消息的用户数最少的方案。2 模型假设（1）用户之间不会因为消息的转发而对消息的原创者进行关注，即关注是在初始状态下不会改变的。（2）忽略各条微博影响力的时效性，即微博影响力随时间是不变的。（3）假设所有用户均非长期不上线用户。（4）不考虑同一用户多次转发同一消息的情况。（5）用户只能由关注对象发布后才能看到或转发消息。3 符号说明第个微博用户或微博消息的第个指标标准化后的值为熵权法模型中所得的第个指标的权重第个微博用户或微博消息的第个指标的最终分数第j列数据所属指标的熵值第i个微博用户与第j个微博用户建立起的关注矩阵注：其余符号在文中使用时说明。4 问题分析4.1问题一问题一要求我们分别在2000人和10000人的微博环境下，对用户的影响因子进行定义，并筛选出影响力前十的用户。首先，经查阅文献1，并基于已给数据，我们确定了用户的影响力指标可由名人指标和粉丝指标两项决定，将这两个指标作为一级指标。名人指标又由博主活跃度和粉丝数量两个指标决定。而粉丝指标又由粉丝活跃度和粉丝专注度两项指标决定。将这四个指标作为二级指标（如图1所示）。其中，活跃度由博主或粉丝发布或转发微博数量反映。图1 用户影响力评价指标体系其次，根据选好的指标，我们通过matlab程序对已给数据进行统计，求出各用户所关注的人数，发布或转发的微博数量，以及各用户被关注的人数。然后对各项指标下的数据进行标准化处理，作为各用户各项指标的得分，使用熵权法算出各项指标的权重。最后，将各指标下的分数与权重相乘，再将各指标下处理后的分数相加，作为各用户影响力评判的最终得分。根据分数高低进行排序，筛选出影响力为前十的用户。图2 问题一思路流程图4.2 问题二 问题二要求我们确定评价微博消息影响力的指标，并依照这些指标进行评分，进而排序和筛选出影响力前十名的消息。首先，由题意可知，微博消息影响力主要由微博被转发次数和转发人的影响力决定。所以，我们将这两个因素作为评价微博消息影响力的两个指标。并且，对各条微博消息被转发次数以及所有转发人的影响力进行统计，得到统计结果。其次，我们将得到的统计结果进行数据的标准化处理，得到两指标下的处理后的分数。再利用熵权法求出两项指标的权重。最后，将权重与各指标分数相乘，对各指标分数求和，得到各条微博消息的影响力评分，将其排列并筛选出影响力前十名的消息。4.3 问题三问题三要求我们求出2000人和10000人环境下的最大好友圈，这实则是最大团问题。首先，根据定义好友圈中的每个人都和圈中其余的人互相关注，所以，构成好友圈的用户一定有好友，即和某人互相关注。由此，我们可以缩小数据规模，只考虑存在相互关注情况的用户，故可将两两关注的情况可以列出。本文则采用循环算法从小到大找到最大的好友圈。其次，若已知两人构成好友圈，若有第三人与这两人构成好友圈，就说明第三人与这两人都相互关注。如此类推至第四人，第五人至第N人，直至已有人的朋友圈内的任意一个人都找不到个人加入该好友圈，则该好友圈已为最大好友圈最后，我们通过不断循环求解，得到在2000人微博用户环境下最大好友圈内人数为10人，10000人微博用户环境下最大好友圈内人数为13人。图3 好友圈确立示意图4.4 问题四问题四要求我们求出在发布某消息的用户数最少的情况下，使所有用户都能看到的最少用户数量。首先，将用户发布消息与微博用户之间相互关注的情形转化为0-1矩阵，分别表示为x和A。这样若某用户能看到消息，则矩阵x与A转置后的矩阵乘积大于等于1。然后，我们将其推广至所有用户，将该问题转化为以发布消息的人数最小值为目标函数，以x与A的乘积全部为1的列矩阵为约束条件的优化问题。最后，使用遗传算法和贪婪算法对其求解即可。5 模型建立与求解5.1 问题一的模型建立与求解5.1.1 数据统计经查阅文献，我们已确立了将博主活跃度和粉丝数量，粉丝活跃度和粉丝专注度作为我们的二级指标，也是我们需要统计的对象（统计结果如下列表格所示，表1至表4为2000人微博环境下各指标统计结果，表5至表8为10000人微博环境下各指标统计结果，所有表格只展示用户编号为前50名的结果）。表1 博主粉丝数量的统计结果（2000人微博环境）用户编号粉丝数量（单位/个）用户编号粉丝数量（单位/个）12626262222718323281142129175233032618311972132258213321925342410133522112636231219372013333820142739221523401716294126172142251826431919214426202845182128462522114722232048222417491725155027表2 用户发布或转发微博数量的统计结果（2000人微博环境）用户编号用户微博数（单位/个）用户编号用户微博数（单位/个）12526212272720328281842729215283024623312672732268243319929342410173521112636281221372613213823142839301526402016344121172942221820432319214425202645202125461622184727232048252423493125275030表3 用户粉丝发布或转发微博数量的统计结果（2000人微博环境）用户编号粉丝活跃度用户编号粉丝活跃度1984262592943273673367288254484299845804305386325312517466325308705333129256345041031735591111303655712922378901373138278144543920115204405951656741725174144229618356434191926244583202254557521487469752251347769236284883424825495182566050951表4 用户所关注他人人数的统计结果（2000人微博环境）用户编号粉丝专注度用户编号粉丝专注度19342629328612735533272875144872982457383048763243126474443258386553328892743449810300355601110936546129913784913755382851449139189152134060616618416971735942266183634337719260445212024245639214424610202248447805236104877924764494922566050931表5 博主粉丝数量的统计结果（10000人微博环境）用户编号粉丝数量（单位/个）用户编号粉丝数量（单位/个）282278639028804932990593307469531757743273887338598734881083358011963691127137781381387714873991151064086168841841788427918994374198744752010445882182467122824772238148912488498425895082表6用户发布或转发微博数量的统计结果（10000人微博环境）用户编号用户微博数（单位/个）用户编号用户微博数（单位/个）15226592612740345285244929435333051650315774332458433358956345810453555114436581246374013553856144639491546403816564151174142521842435819544443203445452136464422504748235048492454493525475058表7 用户粉丝发布或转发微博数量的统计结果（10000人微博环境）用户编号粉丝活跃度用户编号粉丝活跃度1641126885276222722033428928178043450297850511493077676629317466744273275988408733212791085345893101259356369117923666501264933762971341613812921424363961141555944022621632914162751769704255961867594315611927264451772049564510582140554621342211454777632316754878024312349781256481507484表8 用户所关注他人人数的统计结果（10000人微博环境）用户编号粉丝关注度用户编号粉丝关注度111416261615213339274463689628373846439291453152094301353661021311393078727321385588257333881918283410709102231351227911120836117541211727371113013747038223714390139111681592654039561659214111113171214642963718115214330971947374494952093784517622171034638902223554714268232777481282244955491272251147450145295.1.2影响力评价模型的建立鉴于指标集都是有具体的数据，我们采用客观赋权的方法熵权法，对各个指标进行赋权，进而建立线性综合评价模型。熵权法熵权法23是根据被评价对象的指标值构成的判断矩阵来确定指标权重的一种方法，具有较强的客观性，可以排除了不同人的主观影响因素，使评价过程的透明性，再现性，结果客观性高、可行性好。当测评者的熵值达到最大值1，熵权为0，这意味着该测评者没有提供任何有用信息；当各被评价对象在某一指标上的值差异较大时，熵值较小，熵权较大，这表示该指标提供了较多的有用信息。因子的权重系数越高说明该因子对用户影响力得分影响越大。利用熵权法确定影响因素的权数步骤如下：1.数据标准化处理构建判断矩阵，再对其进行标准化处理。判断矩阵： （1） 其中：表示评价的对象数，表示评价的指标数。标准化： （2）其中， 、分别表示同一评价指标下不同对象中粉丝数或活跃度最大或最小者。2. 熵权法求指标权重根据熵的定义，确定所有评价指标的熵值。 （3）式中： 。显然，当时无意义，因此对加以修正，并对其归一化： （4）3. 利用熵值计算评价指标的熵权： （5） （6）4. 指标分数的最终求解(7)5.1.3 模型求解将统计数据代入到模型中，得到各指标的权重（见下表表10）表10 四个指标对应的权重粉丝数量博主活跃度粉丝活跃度粉丝专注度2000人微博环境0.38030.04230.28540.291910000人微博环境0.0970 0.03150.43410.4374将权重与标准化处理以后的分数相乘，分别得到2000人和10000人微博环境下各用户最后的影响力分数，将其按高分到低分排序，如下表表11，表12（表格只显示排名前50位的用户影响力得分）所示：表11 2000人微博环境下各用户最终得分 排名用户编号影响力得分 排名用户编号影响力得分 112354.0179263680.770228313.10942717890.7626317402.956287240.758749472.72862911120.757255372.5613306930.7543613602.39523119540.7514718462.2914322830.7487811232.0499336240.7455914802.01183414390.7452106411.788935830.74481115711.7833366310.74181216391.64693717140.7396134561.25783813630.7388142311.160439810.7384155610.91064018470.7364167870.9068419450.7351178250.81844218290.73311810520.796434970.73271918420.78544415140.7321201030.78374518150.7316219110.7795464420.73082216220.77614711910.7304233660.772748460.7282417000.770949500.72682518590.7705502480.7268注：红色框内为排名前十位的用户编号及其影响力得分。表11 10000人微博环境下各用户最终得分 排名用户编号影响力得分 排名用户编号影响力得分176220.3192613010.1788211090.30872771620.1788330010.30322814750.1788414200.28742977390.1785528730.22273074370.1785665210.2222311890.1783776210.21493221890.178282340.1863354120.178294042017821099650.18135745601809365453018043772210180338241601839482101799402957017984148930.17761737401775184687017741975200177220325501772213077017672245370.1793473850.1767232901767243800.179497375017895069350.1765注：红色框内为排名前十位的用户编号及其影响力得分。5.2 问题二的模型建立与求解5.2.1 数据统计表12 微博被发布或转发数量的统计结果（2000人微博环境）微博编号转发数量微博编号转发数量1493267362750278453442835449482937577730485657314767361321948500331649441349441029435643111433658124483756413345381014916393491559940538163854170517107421461834343527192834460720686457892158446218227814749323754873424120496542576250469表13 微博转发用户影响力的统计结果（2000人微博环境）微博编号转发用户影响力微博编号转发用户影响力1241.600126362.60692368.202727416.4451320.210928172.7334467.96392917.26845381.84530237.4445627.284431233.12997176.24513293.39128245.56533380.24569215.540134463.696910143.310335317.42171169.65693627.665912219.246937277.525213168.0133384.760414449.45639170.06215295.533140265.252816188.42654146.7211751.88534271.318418167.174543258.206219138.385644299.288620337.737345388.046221287.802246105.192722383.913847241.60012335.475948361.39992458.047549322.780925374.607150229.3873表14 微博被发布或转发数量的统计结果（10000人微博环境）微博编号转发数量微博编号转发数量15332682622227376334528702416142939651247301813698331182371493213258373317159596349861026635106511162366641213463777013186238102714542395411548240202165054152117799421147181457431715191504485420140245925213294669522164347181023701481561245649112225417501378表15 微博转发用户影响力的统计结果（10000人微博环境）微博编号转发用户影响力微博编号转发用户影响力153.19162682.879522.02132737.7113334.32722870.78114161.04762940.12925124.307830180.4258698.067831181.4657714.960932132.17783.757533170.9861959.66663498.42191026.147135106.69821116.38493667.073212134.31383777.145713185.407838102.90781454.23753954.20351548.59054020.51581650.73974152.06281780.094742114.422318145.078443170.98611915.02244485.251420139.78664592.46812133.22244669.976522163.830647180.1072370.677348155.799245.566449112.04982542.354350137.30565.2.2 模型求解将统计结果代入问题一所建立的模型中，得到如下结果：表14 两个指标对应的权重微博转发次数转发用户影响力20000.49670.5033100000.50190.4981将权重与标准化处理以后的分数相乘，分别得到2000人和10000人微博环境下各条微博最后的影响力分数，将其按高分到低分排序，如下表表15，表16（表格只显示排名前20条的微博影响力得分）所示：表15 各微博影响力得分（2000人微博环境）序号微博编号微博影响力得分19020.503627719.900935319.82224419.452953419.322765119.085371418.739489818.398695618.3424109617.9323112717.3252127417.2089137616.6878147016.6314158216.3798165416.232174516.1602185516.1428196516.0308202215.9922注：红色框内为排名前十位的微博编号及其影响力得分（下同）表16 各微博影响力得分（10000人微博环境）序号微博编号微博影响力得分1714.09182694.064934664.063244494.04453753.98161293.977171173.957482073.946491623.946410593.9464112143.9443124413.928813723.9182144193.9138152213.9036164433.9002171843.896181043.896191463.8768201553.86365.3 问题三的模型建立与求解5.3.1 相互关注模型建立1.筛选两两关注的用户 将定义为关注情况矩阵，即第用户关注第用户的情况。所以，则为第用户关注第用户的情况。所以，两两关注矩阵则可写为（8）2.筛选多人相互关注的用户加入第三个用户x，再次判断若M(x,i)=M(x,j)=1，则三三用户即为好友圈，反之，则不是，将不和条件用户去除，将符合要求的用户编入新的组。加入第四个用户y，再次判断若M(y,i)=M(y,j)=1，则四四用户即为好友圈，反之，则不是，将不和条件用户去除，将符合要求的用户编入新的组。如此不断进行，当再无符合条件的用户加入时，我们就认为达到最大好友圈。此时结束程序，返回结果。5.3.2 模型求解将表格中数据代入上述模型后，得到结果如下：表17 最大好友圈结果最大好友圈类型用户ID2000个用户（共10个）336 103 366 561 787 911 1164 1218 1276 185910000个用户（共13个）2529 867 2886 3077 3206 3222 3646 4012 4831 5630 6241 7408 88575.4 问题四的模型建立与求解5.4.1 0-1规划模型建立令，其中，假设被关注矩阵，假设被关注矩阵A对角线元素也为1，那么则表示第j个用户看到消息，否则第j个用户看不到消息。现要使所有用户都看到，那么对任意j，都要满足上述条件，用矩阵表示形式为：(9)所以可以将问题转化为0-1规划问题，即 (10)5.4.1 模型求解用matlab自带的遗传算法解上述0-1规划问题，程序见附录。对于系统1，经过多次重复计算，发现f最小值一直在500多次左右，远大于下述的贪心算法计算出的93次，用遗传算法效果不是很好。5.4.2 贪心算法模型算法简介：本题要求给出发布消息人数最少的分配方案，采用贪心算法，查找关注当前消息发布用户的粉丝中信息扩散能力最大的一个用户作为信息发布者，通过逐步添加发布信息用户，扩大信息接收群体，直至找到第一个满足所有用户均看到此消息的方案为止。算法步骤：1. 初始化发布消息用户为当前被关注量最大的用户。2. 初始化已经能够看到消息的用户群体为当前发布消息用户和该用户粉丝。3. 查找尚未发布过信息的用户中，能够使除去已经能看到此消息的粉丝数量最大，把该用户作为信息发布者，同时更新能够看到消息的用户群体。4. 判断当前能看到消息的群体是否已覆盖所有人，如果为真，则结束算法，当前发布信息者集合即为找到的最少发布信息群体；如果为假，则转到3。计算结果：根据data1.xls数据，计算2000用户中最少用户发布消息覆盖全部用户的结果，得出计算结果：发布信息用户个数为93，下列为发布信息用户的编号：2493241475054617074115122130150157165184202204207222231269270273305324338349355368382386388393394399431442446456460475512532537550577602613624631641654655699726754774825831872909917947103310391080112311441235125812881289134013601383139614011473148015711595162116221639174018461889189119741985根据data2.xls数据，计算10000用户中最少用户发布消息覆盖全部用户的结果，得出计算结果：发布信息用户个数为249,下列为发布信息用户的编号：279287290296314318322329354398427430431439459468478491527529538540587591604618623652658697706718725727750788802813818836841859865868878892895935950986100610151043106410731083110911241143115111711209122412381240124312881328133313961420143114501481159015981599161916211648168118001852190919191974198220052011201220342066214921542169219322042341238824492458249524962586259726582670278328282873295229532963298830013002301531193150315231743362355636023643368637203785382238323841385039123967398840044027404040764101412042544277428844354588462846844734477048534929497349954997505551065144520152425276536753915439553755475553560460286053606660716371639364356440644264466521657265986703674767506919696470347048708872237408740974547483762176227649772077577766778378237844789080138016812081768211828384838514856386408684873287498809882789999086920692739289930993469458954796506 模型的评价与推广6.1 模型的优点（1）高效简便。采用Matlab7.8等专业软件对模型进行求解，使运算更为简便快捷，效率更高；（2）结果可靠。本文建立的熵权模型,0-1规划矩阵模型等能有效避免运算繁杂等问题，使结果更加合理可靠。 (3）模型简单易懂，方法灵活，具有较强的推广性。6.2 模型的缺点由于题目所给数据类型较少，本文在研究影响力等问题时，并未考虑实际微博中的评论，多次转发，点赞等微博功能对微博用户影响力等各方面的影响。6.3 模型的推广本文在建立影响力评价模型中，能巧妙运用贪婪算法等多种算法对模型进行求解。可广泛用于双星定位、模式识别等实际问题中，有较强的推广性。参考文献1 刘雁妮，贺和平等，名人微博的影响力评价指标研究，武汉理工大学学报，2012.34（6） 2李俊，基于熵权法的粮食产量影响因素权重确定，安徽农业科学，2012,40(11):6851-6854.3韩中庚，数学建模方法及其应用，北京：高等教育出版社，2005.6.4刘志刚, 王建华, 耿英三, 等. 一种改进的遗传模拟退火算法及其应用J. 系统仿真学报, 2004, 16(5): 1099-1101.5姜启源，数学模型（第二版），北京：高等教育出版社，1993.附录（所有程序软件均为Matlab 7.8）问题一 对每位用户影响力进行综合评价的程序clear allclcA=;%FSnum统计每位用户粉丝数A=xlsread(XGdata1.xls);FSnum=zeros(1,2000);for i=1:2000 FSnum(1,i)=nnz(A=i);end B=;%WBnum统计每位用户所发微博数B=xlsread