江西省数学建模大赛试题.doc.pdf

《江西省数学建模大赛试题.doc.pdf》由会员分享，可在线阅读，更多相关《江西省数学建模大赛试题.doc.pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1.问题重述2.问题分析3.问题一的建模过程3.1.模型的基本假设a个体 i接收或发出的 Email的数呈越多，则个体 i的重要性程度越高。 b与个体 i有 Email联系的其他个体的数量越多，则个体 i的重要程度越高。 c与个体 i有 Email联系的其他个体的重要性程度越高，则个体 i的重要程度越高。3.2.数据的删选在对大量数据进行处理，挖掘有川信息的过程中，数据筛选是必不可少的步骤。在不影响分析结果质量的前提丁，对数据信息进行初步、粗略的筛选，以大大的节省时间，提高 模型运算的效率。对于第一组数据， 我们发现有很多个体从未与其他个体进行 Email联系， 即收 （发） Email的数量

2、为零，或者与其他个体进行 Email 联系的次数非常少，那么根据前面假设，这些个体 的重要性程度必然不高。因此，我们设定一个阈值，选収收（发） Email总数量大于阈值的个 体的数据作为分析依据。阈位的没置川以排除掉认为是偶然事件产生的噪声数据或者是对整 个分析影响不大的数据，简化模型的求解过程。需要注意的是，阈值不宜过大，不然会带来 网络结构的损坏，从而改变求解社团结构核心成员的结果。在这里，我们经过综合考虑，所 选取的阀值为 100,从而生成一个新的 50X50的安然公司高管通讯数据矩阵。对于第二组数据，我们做了同样处理，选取的阀值为6.2355,生成新的 100X100的安 然公司高管紧

3、密程度矩阵。3.3.模型的符号说明AA* 叫BbijDi一一个体 i的度数指标值；Ei一一个体 i的特征向量指标值；Ri个体 i的 Mail Rank指标值；Si一一个体 i的重要性指标值；3.4.模型的建立针对方法一所构建的人物关系网络，要想得到网络屮的关键人物，实际就是要对每一个 个体进行重要性程度的排序。对此，我们做了以下工作：Stepl：求个体 i的度数指标值度数（Degree）是评估复杂社会网络个体重要性最简单直接的指标，通常对于人们最直观的认识就是网络中度数最大的个体就是网络中最重要的成员。对于某个体的度数Di，是指 与该个体有 Email通讯联系行为的其他个体数量，即：公式 1S

4、tep2：求个体 i的特征向量指标值特征向量(Eigenvector)指标是评估复杂社会网络个体重要性的另一个著名的指标， 度指 标把与之联系的个体看为同等重要，而实际上个体之间是不平等，必须考虑到与之联系的个 体本身的重要性对该个体的重要性的影响。如果一个与之联系的个体很重要，那么这个个体 很可能重要性高：如果与之联系的个体重要性不是很高的话，那么即使与该个体联系的其他 个体众多，该个体也不一定很重要，通常称这种情况为邻居个体的重要性反馈。特征向量指 称针对这一实际情况，把网络中某个个体的重要性程度看成邻居个体重要性的一个线性叠 加。特征向馇指标是网络的邻接矩阵对应的最大特征俏.的特征叫量，

5、每一维即为对应个体的 重要性，若 la 最人特征值(也称为主特征值)，公式 2砂为矩阵 A对应儿的特征向呈，那么有 公式 3对应到每一个个体的特征向量指标为：公式 4Step3：求个体 i的 Mail Rank指标伉Page Rank 算法是 google公司的创始人 Larry Page 和 Sergey Brin 提出的网页排名算法， 它是搜索引擎 google的核心技术之一。Page Rank算法将文献检索中的引用理论用到 web中，引川网页的链接数，一定程度上反映丫该网贞的重要性和质量。每个到页面的链接都是 对该页面的一次投票，被链接的越多，就意味着被其他网站投票越多，google用

6、Page Rank值来标识每个网页的重要性，以此来对检索出的网页进行排名，如果一个网页被很多其它网 页所链接，说明它受到普遍的承认和信赖，那么它的 Page Rank 值也越高。基于这种思想， 我们定义复杂社会网络中个体 i的 Mail Rank指标值为个体 i接收或发山的 Email的总数量， 即：公式 5Step4：求个体 i的重要性指标值由于我们在最终确定个体 i的重要性的时候选考虑了度数指标、特征向量指标和 Mail Rank指标，因此个体 i的重要性指标值是以上三个指标值统一量纲之后的加权值，即：公式 6针对方法二所构建的人物关系网络，考虑到题目所列数裾的特点，和方法一的处理方式 类

7、似，我们做了以下工作：Stepl：求个体 i的度数指标值Step2：求个体 i的 Mail Rank指标值Step3：求个体 i的重要性指标值3.5.模型的求解4.问题二的建模过程4.1.两种方法所构建的人物关系网络对组织结构关系刻画的利弊分析4.1.1.方法一分析方法一是基于通信行为的人物关系网络构建，即人物关系的建立是基于通信行为的，这 是指如果两个人之间的通信次数越高那么二者之间的关系就越紧密。对于这种人物关系构建 方法的优点如下：首先，数裾的可获得性良好，因为只是对两个个体之间是否发生通信行行为以及通信的 次数进行统计，可以更容易地获取数据。通过提取邮件头的 From和 To字段，可以

8、得到隐 含在收件人与发件人之间的地址收发关系，利用这种收发关系，构建邮件地址通联关系|xxj络, 进而从网络分析的角度去处理和挖掘邮件网络节点之间的关系。其次，数据的可靠性良好，现代的统计手段和方法可以很好地保证数据的真实性和准确 性，从而为后续的数据挖掘打下良好基础。电子邮件地址关系形成的网络具有许多其他社会 网络无法比拟的真实性，邮件通联关系网络可以上升到邮箱用户空间，构建映射关系来挖掘 邮箱用户之间的社会关系，因此构建邮件通联关系网络不仅对邮件数据挖掘和分析十分有意 义，同时也对邮箱用户社会关系的研究提供了基础。再次，通信次数与个体之间的紧密程度的关联程度较高，一般来说，两个人之间的关系

9、 越密切，那么他们通信的频率就会越高。最后，数裾所蕴含的信息丰富，电子邮件提供了丰富的个人通信甚至组织通信数据，并 且通过垃圾邮件过滤处理后的邮件具有较高的可信性，另外电子邮件的通信格式采用相对标 准的电子格式，使得对这些数据的处理相对简单。用通信行为来描述个体之间的关系，所得 出的通信次数矩阵以及进行简化后的 0 1 矩阵，可以做复杂社会网络核心成员分析和复杂 网络社 M发现分析等多种社会网络关系分析，而在问题中，我们利用这种方法所构建的人物 关系网络通讯次数矩阵来发现核心人物，也得到了较好的验证。缺点.首先，可能会忽略某些个体的个人习惯所造成的偶然性因素，晋如有些人不喜欢使用Email这种

10、通讯手段，而采取电话或者面谈的形式来和自己的上下级或者朋友进行交流，那 么基于这种方法所构建的人物关系网络可能会出现缺失，甚至会漏掉某个关键人物，从而影 响整个关系网络的结构。其次，没有考虑通信行为的方向性。例如 A 向 B 发出 100 封邮件，而 B 没有回复 A 的 邮件，那么可能 A与 B的关系相对就不那么紧密；如果 A向 B发出 50封邮件，B同样回 复 A50封邮件，那么 A和 B的关系可能比前面的情况会更紧密。再次，没有考虑通信行为发生的具体形式对个体之间紧密程度的影响。邮件的发送方式 则分为以下儿种：向一个地址发送邮件；向多个地址发送邮件；抄送；暗送；定 吋发送；转发。从以上列

11、出的发送方式，分析知道两个邮件地址之间的通联关系包括直接 通联和间接通联两种关系。最后，忽略了通信的内容。两个个体之间可能会因为工作关系通信，或者其他的原因， 或者仅仅只是转发第三人的邮件，这些都会对两者的紧密程度产生影响。4.1.2.方法二分析方法二是基于邮件内容的人物关系网络构建，人物关系的建立是基于邮件内容的，这是 指假设两个人在 N篇邮件内同时出现过，如果 N越大，那么二者的关系就越紧密。方法二 的优点如下：首先，电子邮件记录了通信的内容，通过文本处理和挖掘技术，可以对邮件进行总结 , 按话题进行归类，可以了解邮箱用户的兴趣，发现具有共同兴趣的社团。邮件网络节点具有 话题属性，节点每发

12、送一次邮件，总是在传递某些内界，通过对其某吋段内发出的邮件进行挖掘分析，可以得到节点的话题信息。其次，节点对通过收发邮件产生通联关系，通过对边上的邮件内容进行提取和分析，可 以得到边上的话题属性。提取某时段 A该边上通信的所有邮件的 A容信息，对其进行分析得 到边的话题。由于在较短时间內边上的话题趋于集中，于是结合所有相关邮件的Subject字 段和正文内容信息得到边上的话题，边的话题属性是没有方向的。最后，基于邮件内容分析的方法，可以根据耑要获取具有更强目的性的数据，例如在已 知某个疑犯的情况 T 根据其在犯罪网络中的位置推断出整个网络的信息流动和犯罪计划，用 以打击犯罪活动等，具有更实际的

13、意义。缺点：首先，数据获得的工作量比较大，Subject字段和正文内容信息得到边上的话题可能需 要在海里文本里面检索有川信息，费时费力。有时候，可能所获取的信息的价值，与収得信 息的成本不相匹配，这样就失去了数据挖掘的意义。其次，基于邮件 A容来发现数据的方法在推广过程屮可能会遇到跨语言的障碍，因为不 同的语系具有不同的特点，同样一种数据挖掘的方法，可能在不同的语言之间会产生不同的效用。4.1.3.方法一与方法二的对比电子邮件在各种社会组织和个人通信联系中具有广泛的应川，并且电子邮件数据具有 区别于文本数据的特性，这使其成为研宂大量社会关系网络结构的有价值的资源。研宂邮 件数据相关特性、解析邮

14、件数据为研究邮件关系网络提供了基础。4.2.人物关系网络中的群集行为的挖掘4.2.1.模型的假设a两个体的紧密程度越高，那么他们处于同一个子网的可能性就越大b任意两个直接关联的个体之间的路径长度是一样的。c个体的重要性指标值越高，那么他处于子网中心位置的可能性越大。4.2.2.数据的预处理邮件数据屮蕴涵有大量重要有价值的信息，人们在利用邮件通讯的同时，把社会关系也 隐含在了电子邮件之中，邮件不但记录了人们之间的关系，而且提供了通讯频率、通讯吋间、 社交范围、通信内容等特征，利用这些特征可以构建有权的邮件通联关系网络；通过对邮件 记录的内容进行文本分析和挖掘，可以将不同类型的社会关系进行分类；通

15、过对邮件获取的 时间维数分析，还可以帮助我们观察网络结构的动态特性。针对问题一的两种方法，一是对邮件地址的挖掘；二是对邮件内容的分析，但仅仅使用 其中的一种方式对邮件分析是不够全面的。因此，我们结合两种处理方式，充分利用邮件数 据的特点，在问题一计算结果的基础上，结合邮件头地址信息和文本内容信息，采用以关键 人物为核心的邮件联通子网络的抽取方法，來构建社会网络中的子网络分布情况，來挖掘人 物关系网络屮的群集行为。由于方法二的数据是基于对邮件内容的分析所得到的，因此存在人名的对应关系混乱的 问题，所以我们仍以方法一的数据资料的人名为标准，综合考虑两个数据的紧密程度指标, 重新设定阀值，构建 10

16、0X100矩阵 C,矩阵巾的元素为综合考虑两个数据之后，经过调整的紧密程度值。因此，我们以矩阵 C为输入数据，并选取问题一的分析结果中的关键人物之一 lay-k作 为起点，构建邮件联通子网络的抽取模型。4.2.3.模型的符号说明CCij1Arfbta4.2.4.Steph设定 lay-k与其联系人的紧密程度阀值模型的建立基于通联关系网络节点间通信的紧密程度，子网抽取的思路是利用边的权值来刻画节 点间的关系。对每一层节点，选择边的权值达到阈值的节点加入到子网中。首先给定边权值 的初始阈值；以选定的重要节点为中心节点，将其作为第一层扩展的边权行判断，若该节点 与中心节点之间边的权依大于阈伉，将该边

17、和节点加入伉的阈伉。AAStep2：剥离紧密程度较小个体以选定的重要节点为中心节点，对中心节点直接相邻的节点进行判断：若该节点与中心 节点之间边的权值大于阈值，将该边和节点加入关联子集中。对该层扩展过程中所有加入子 网的边的权值取平均值，将其作为下一层扩展的边权值的阈值。AAStep3：对新加入的个体进行扩展重复以上过程，对所有新加入子网的中心点进行分析，对其关联的边的权值进行判断, 按边权值大小依次进行处理。选择未处理节点中关联边权值最大的节点，若与其相连的边上 的权伉达到新的阈伉并且尚未在子网屮，则将其加入子网，同时将其连接的节点也加入到关联子集中，直到没有符合条件的边和节点加为止。Step4：扩展终止若算法收敛，即该层不存在满足阈值的边则扩展终止，或者达到给定:步长深度值或者最 大抽取的网络边数，则扩脱终止。根据六度分割理论(Six Degrees of Separation)，一个人和 任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过六个人你就能够认识任 何一个陌生人。因此，我们选取的最大抽取网络边数为 6。AA4.2.5.模型的求解