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

1. 问题重述2. 问题分析3. 问题一的建模过程3.1. 模型的基本假设a 个体i接收或发出的Email的数量越多，则个体i的重要性程度越高。b 与个体i有Email联系的其他个体的数量越多，则个体i的重要程度越高。c 与个体i有Email联系的其他个体的重要性程度越高，则个体i的重要程度越高。3.2. 数据的删选 在对大量数据进行处理，挖掘有用信息的过程中，数据筛选是必不可少的步骤。在不影响分析结果质量的前提下，对数据信息进行初步、粗略的筛选，可以大大的节省时间，提高模型运算的效率。对于第一组数据，我们发现有很多个体从未与其他个体进行Email联系，即收（发）Email的数量为零，或者与其他个体进行Email联系的次数非常少，那么根据前面假设，这些个体的重要性程度必然不高。因此，我们设定一个阈值，选取收(发)Email总数量大于阈值的个体的数据作为分析依据。阈值的设置可以排除掉认为是偶然事件产生的噪声数据或者是对整个分析影响不大的数据，简化模型的求解过程。需要注意的是，阈值不宜过大，不然会带来网络结构的损坏，从而改变求解社团结构核心成员的结果。在这里，我们经过综合考虑，所选取的阀值为100，从而生成一个新的50X50的安然公司高管通讯数据矩阵。对于第二组数据，我们做了同样处理，选取的阀值为6.2355，生成新的100X100的安然公司高管紧密程度矩阵。3.3. 模型的符号说明AA* aij B bij Di个体i的度数指标值； Ei个体i的特征向量指标值；Ri个体i的Mail Rank指标值；Si个体i的重要性指标值；3.4. 模型的建立针对方法一所构建的人物关系网络，要想得到网络中的关键人物，实际就是要对每一个个体进行重要性程度的排序。对此，我们做了以下工作：Step1：求个体i的度数指标值度数(Degree)是评估复杂社会网络个体重要性最简单直接的指标，通常对于人们最直观的认识就是网络中度数最大的个体就是网络中最重要的成员。对于某个体的度数Di，是指与该个体有Email通讯联系行为的其他个体数量，即：公式1Step2：求个体i的特征向量指标值特征向量(Eigenvector)指标是评估复杂社会网络个体重要性的另一个著名的指标，度指标把与之联系的个体看为同等重要，而实际上个体之间是不平等，必须考虑到与之联系的个体本身的重要性对该个体的重要性的影响。如果一个与之联系的个体很重要，那么这个个体很可能重要性高；如果与之联系的个体重要性不是很高的话，那么即使与该个体联系的其他个体众多，该个体也不一定很重要，通常称这种情况为邻居个体的重要性反馈。特征向量指标针对这一实际情况，把网络中某个个体的重要性程度看成邻居个体重要性的一个线性叠加。特征向量指标是网络的邻接矩阵对应的最大特征值的特征向量，每一维即为对应个体的重要性，若la最大特征值(也称为主特征值),公式2砂为矩阵A对应几的特征向量,那么有公式3对应到每一个个体的特征向量指标为：公式4Step3：求个体i的Mail Rank指标值Page Rank算法是google公司的创始人Larry Page和Sergey Brin提出的网页排名算法，它是搜索引擎google的核心技术之一。Page Rank算法将文献检索中的引用理论用到web中，引用网页的链接数，一定程度上反映了该网页的重要性和质量。每个到页面的链接都是对该页面的一次投票，被链接的越多,就意味着被其他网站投票越多，google用Page Rank值来标识每个网页的重要性，以此来对检索出的网页进行排名，如果一个网页被很多其它网页所链接，说明它受到普遍的承认和信赖，那么它的Page Rank值也越高。基于这种思想，我们定义复杂社会网络中个体i的Mail Rank指标值为个体i接收或发出的Email的总数量，即：公式5Step4：求个体i的重要性指标值由于我们在最终确定个体i的重要性的时候选考虑了度数指标、特征向量指标和Mail Rank指标，因此个体i的重要性指标值是以上三个指标值统一量纲之后的加权值，即：公式6针对方法二所构建的人物关系网络，考虑到题目所列数据的特点，和方法一的处理方式类似，我们做了以下工作：Step1：求个体i的度数指标值Step2：求个体i的Mail Rank指标值Step3：求个体i的重要性指标值3.5. 模型的求解4. 问题二的建模过程4.1. 两种方法所构建的人物关系网络对组织结构关系刻画的利弊分析4.1.1. 方法一分析方法一是基于通信行为的人物关系网络构建，即人物关系的建立是基于通信行为的，这是指如果两个人之间的通信次数越高那么二者之间的关系就越紧密。对于这种人物关系构建方法的优点如下：首先，数据的可获得性良好，因为只是对两个个体之间是否发生通信行行为以及通信的次数进行统计，可以更容易地获取数据。通过提取邮件头的From和To字段，可以得到隐含在收件人与发件人之间的地址收发关系，利用这种收发关系，构建邮件地址通联关系网络，进而从网络分析的角度去处理和挖掘邮件网络节点之间的关系。其次，数据的可靠性良好，现代的统计手段和方法可以很好地保证数据的真实性和准确性，从而为后续的数据挖掘打下良好基础。电子邮件地址关系形成的网络具有许多其他社会网络无法比拟的真实性，邮件通联关系网络可以上升到邮箱用户空间，构建映射关系来挖掘邮箱用户之间的社会关系，因此构建邮件通联关系网络不仅对邮件数据挖掘和分析十分有意义，同时也对邮箱用户社会关系的研究提供了基础。再次，通信次数与个体之间的紧密程度的关联程度较高，一般来说，两个人之间的关系越密切，那么他们通信的频率就会越高。最后，数据所蕴含的信息丰富，电子邮件提供了丰富的个人通信甚至组织通信数据，并且通过垃圾邮件过滤处理后的邮件具有较高的可信性，另外电子邮件的通信格式采用相对标准的电子格式，使得对这些数据的处理相对简单。用通信行为来描述个体之间的关系，所得出的通信次数矩阵以及进行简化后的01矩阵，可以做复杂社会网络核心成员分析和复杂网络社团发现分析等多种社会网络关系分析，而在问题中，我们利用这种方法所构建的人物关系网络通讯次数矩阵来发现核心人物，也得到了较好的验证。缺点：首先，可能会忽略某些个体的个人习惯所造成的偶然性因素，譬如有些人不喜欢使用Email这种通讯手段，而采取电话或者面谈的形式来和自己的上下级或者朋友进行交流，那么基于这种方法所构建的人物关系网络可能会出现缺失，甚至会漏掉某个关键人物，从而影响整个关系网络的结构。其次，没有考虑通信行为的方向性。例如A向B发出100封邮件，而B没有回复A的邮件，那么可能A与B的关系相对就不那么紧密；如果A向B发出50封邮件，B同样回复A50封邮件，那么A和B的关系可能比前面的情况会更紧密。再次，没有考虑通信行为发生的具体形式对个体之间紧密程度的影响。邮件的发送方式则分为以下几种：向一个地址发送邮件；向多个地址发送邮件；抄送；暗送；定时发送；转发。从以上列出的发送方式，分析知道两个邮件地址之间的通联关系包括直接通联和间接通联两种关系。最后，忽略了通信的内容。两个个体之间可能会因为工作关系通信，或者其他的原因，或者仅仅只是转发第三人的邮件，这些都会对两者的紧密程度产生影响。4.1.2. 方法二分析 方法二是基于邮件内容的人物关系网络构建，人物关系的建立是基于邮件内容的，这是指假设两个人在N篇邮件内同时出现过，如果N越大，那么二者的关系就越紧密。方法二的优点如下： 首先，电子邮件记录了通信的内容，通过文本处理和挖掘技术，可以对邮件进行总结，按话题进行归类，可以了解邮箱用户的兴趣，发现具有共同兴趣的社团。邮件网络节点具有话题属性，节点每发送一次邮件，总是在传递某些内容，通过对其某时段内发出的邮件进行挖掘分析，可以得到节点的话题信息。其次，节点对通过收发邮件产生通联关系，通过对边上的邮件内容进行提取和分析，可以得到边上的话题属性。提取某时段内该边上通信的所有邮件的内容信息，对其进行分析得到边的话题。由于在较短时间内边上的话题趋于集中，于是结合所有相关邮件的 Subject 字段和正文内容信息得到边上的话题，边的话题属性是没有方向的。最后，基于邮件内容分析的方法，可以根据需要获取具有更强目的性的数据，例如在已知某个疑犯的情况下根据其在犯罪网络中的位置推断出整个网络的信息流动和犯罪计划，用以打击犯罪活动等，具有更实际的意义。缺点：首先，数据获得的工作量比较大，Subject 字段和正文内容信息得到边上的话题可能需要在海里文本里面检索有用信息，费时费力。有时候，可能所获取的信息的价值，与取得信息的成本不相匹配，这样就失去了数据挖掘的意义。其次，基于邮件内容来发现数据的方法在推广过程中可能会遇到跨语言的障碍，因为不同的语系具有不同的特点，同样一种数据挖掘的方法，可能在不同的语言之间会产生不同的效用。4.1.3. 方法一与方法二的对比电子邮件在各种社会组织和个人通信联系中具有广泛的应用，并且电子邮件数据具有区别于文本数据的特性，这使其成为研究大量社会关系网络结构的有价值的资源。研究邮件数据相关特性、解析邮件数据为研究邮件关系网络提供了基础。4.2. 人物关系网络中的群集行为的挖掘4.2.1. 模型的假设a 两个体的紧密程度越高，那么他们处于同一个子网的可能性就越大b 任意两个直接关联的个体之间的路径长度是一样的。c 个体的重要性指标值越高，那么他处于子网中心位置的可能性越大。4.2.2. 数据的预处理 邮件数据中蕴涵有大量重要有价值的信息，人们在利用邮件通讯的同时，把社会关系也隐含在了电子邮件之中，邮件不但记录了人们之间的关系，而且提供了通讯频率、通讯时间、社交范围、通信内容等特征，利用这些特征可以构建有权的邮件通联关系网络；通过对邮件记录的内容进行文本分析和挖掘，可以将不同类型的社会关系进行分类；通过对邮件获取的时间维数分析，还可以帮助我们观察网络结构的动态特性。针对问题一的两种方法，一是对邮件地址的挖掘；二是对邮件内容的分析，但仅仅使用其中的一种方式对邮件分析是不够全面的。因此，我们结合两种处理方式，充分利用邮件数据的特点，在问题一计算结果的基础上，结合邮件头地址信息和文本内容信息，采用以关键人物为核心的邮件联通子网络的抽取方法，来构建社会网络中的子网络分布情况，来挖掘人物关系网络中的群集行为。由于方法二的数据是基于对邮件内容的分析所得到的，因此存在人名的对应关系混乱的问题，所以我们仍以方法一的数据资料的人名为标准，综合考虑两个数据的紧密程度指标，重新设定阀值，构建100X100矩阵C，矩阵中的元素为综合考虑两个数据之后，经过调整的紧密程度值。因此，我们以矩阵C为输入数据，并选取问题一的分析结果中的关键人物之一lay-k作为起点，构建邮件联通子网络的抽取模型。4.2.3. 模型的符号说明CCijiArfbta4.2.4. 模型的建立 Step1：设定lay-k与其联系人的紧密程度阀值 基于通联关系网络节点间通信的紧密程度，子网抽取的思路是利用边的权值来刻画节点间的关系。对每一层节点，选择边的权值达到阈值的节点加入到子网中。首先给定边权值的初始阈值；以选定的重要节点为中心节点，将其作为第一层扩展的边权行判断，若该节点与中心节点之间边的权值大于阈值，将该边和节点加入值的阈值。AA Step2：剥离紧密程度较小个体 以选定的重要节点为中心节点，对中心节点直接相邻的节点进行判断：若该节点与中心节点之间边的权值大于阈值，将该边和节点加入关联子集中。对该层扩展过程中所有加入子网的边的权值取平均值，将其作为下一层扩展的边权值的阈值。AA Step3：对新加入的个体进行扩展重复以上过程，对所有新加入子网的中心点进行分析，对其关联的边的权值进行判断，按边权值大小依次进行处理。选择未处理节点中关联边权值最大的