安然公司高管的组织结构挖掘

安然公司高管的组织结构挖掘摘要本文中，我们主要分析和处理安然公司的邮件数据集，进而应用两种方法对安然公司的高层管理者之间的组织结构关系进行了挖掘，找出了其中的关键人物以及网络中的群集行为，并进一步找到了其中可能存在的犯罪嫌疑人。针对问题一，我们根据建立了中心度指标模型，对题目所给数据进行了权值处理，利用Mathematica软件计算出了三种中心度作为指标，再进行聚类分层，从而分别找出了两个网络中的关键人物。针对问题二，我们首先对题目中所给的2307个人物信息进行了分析整合和压缩，很大程度上减轻了工作量也提高了准确性。我们根据问题一中的三度模型指标、基于连接特性的Email社会网络社群挖掘算法和六度分隔定理建立了集群结构挖掘模型，结合第一问找到的关键人物通过计算每个人的紧密中心度，得到了两种网络建立方法下的群集行为。同时，用这样的挖掘方法可以方便快速的找出任意亲密度要求下的群集组成。最后我们利用随机抽取人物进行社群分析的办法还对两种方法进行了比较，认为方法1更为可靠。通过对上一问的解答，对于每一个节点我们都可以得到其分别在两个网络中的性质指标。在对requirement3的求解中，我们兼顾了这两种指标发现几乎所有的高层管理者均参与了欺诈案件，且每一个岗位都存在着参与犯罪的人员。这与我们从纪录片中了解到的背景资料是相一致的。关键词：聚类分层三度模型社会网络社群挖掘算法六度分隔定理1(一)问题重述安然公司（Enron）是一家位于美国得克萨斯州休斯敦市的能源类公司，曾是世界上最大的电力、天然气以及电讯公司之一，公司连续六年被《财富》杂志评选为“美国最具创新精神公司”，然而真正使安然公司在全世界声名大噪的，却是这个拥有上千亿资产的公司2002年在几周内破产，持续多年精心策划、乃至制度化系统化的财务造假丑闻，以及安然事件中的高层管理者欺诈犯罪事件。安然倒闭之后，许多研究者致力于分析与处理安然邮件数据集（包含有150位安然公司高层管理者自2000年至2002年的所有邮件），试图通过分析这个数据集挖掘出安然公司高层管理者之间的组织结构关系（通常也叫做社区结构），并进一步找出其中可能存在犯罪嫌疑人。他们采用了两种建立人物关系的方法初步得到了两个与之对应的人物关系网络（用矩阵来描述，每个元素描述关系的紧密程度，取值范围从0至1,0代表关系最不紧密，1代表关系最紧密）：方法1，基于通信行为的人物关系网络构建：人物关系的建立是基于通信行为的，这是指如果两个人之间的通信次数越高那么二者之间的关系就越紧密；所得人物关系网络为150乘150矩阵，这里的150是Enron高管的人数，详细数据见第一组数据（数据中有两个文件，name.txt为150个人的名字，adjacent.txt表示他们之间的有效通信次数，一般有效通信次数）；方法2：基于邮件内容的人物关系网络构建：人物关系的建立是基于邮件内容的，这是指假设两个人在N篇邮件内同时出现过，如果N越大，那么二者的关系就越紧密。所得人物关系网络为2307乘2307矩阵，这里的2307个人物是邮件内出现的高频人物，详细数据见第二组数据（数据中Namelist2.txt表示人物名字，RalationNet2.mat是matlab文件，表示这2307个人物之间的紧密程度。值得提醒的是由于基于内容分析，有些人物名字上可能有不一致，比如可能是名字全称，也可能只用名或姓，这也需要你们自行分析）。问题：1、分别针对方法1和方法2中的人物关系网络，找出其中的关键人物。2、试分析上述两种方法所构建的人物关系网络对组织结构关系刻画的利弊，结合第一问得到的关键人物，选择其中的一种方法（或是综合两种方法），挖掘人物关系网络中的群集行为。3、若已经知道，Enron公司的三位高管是犯罪嫌疑人（KennethLay：Chairman；JefferySkilling：CEO；AndrewFastowCFO），能否通过以上的组织结构找出可能存在的其他犯罪嫌疑人，高管职位参见附录。(二)问题一2.1分析该问题需要我们找出复杂社会网络中的关键点，本质上是社会网络的结构挖掘问题的一个必经步骤。但是我们所拥有的对象的信息不同于常见的传统的社群2挖掘工作集中在的Web链接网络和科学文献网络，而是E-mail社会网络。方法一和方法二给出了E-mail社会网络的两个不同侧面的信息：通信行为和通信内容。两者的区别在于：方法一所给的矩阵反映了150位高管之间联系的紧密程度，而方法二所给的矩阵由于关联的人数更多，可以确定包括高管在内的从高到低不同层级中人员之间联系的紧密程度。但两个矩阵中的元素本质上都是有关人员两两之间的关系紧密程度。都可以用图论的知识去刻画每一位安然公司员工的重要性。2.2数学模型准备2.2.1邻接矩阵本题附件所给的两个矩阵可视为邻接矩阵。邻接矩阵的定义如下设图(,)GVE的顶点集为123(){,,,...,}pVGvvvv，用ija表示G中顶点iv与jv之间的边数，则n阶方阵()()ijppMGa称为G的邻接矩阵。邻接矩阵是对称矩阵。2.2.2点度中心度点度中心度(degreecentrality)是是一个最简单、最直观的指标，它描述的是一个节点位于图中“核心”位置的程度，刻画了该点与图中其他点发展交往关系的能力。点度中心度分为绝对中心度和相对中心度。对于有n个结点的图(,)GVE，结点v的相对点度中心性()DCv为deg()()1DvCvn其中deg()v为节点v的度，即该点的绝对中心度。在Email社会网络中，如果一个节点的点度中心度很高，说明该点与其他点的交往是比较频繁的，这个点很可能是该网络的核心。2.2.3介数中心度介数中心度(betweennesscentrality)描述的是一个节点起到“中介”作用的程度，它刻画了该点控制图中其他点之间交往关系的能力。介数中心度分为绝对介数中心度和相对介数中心度。对于n个结点的图(,)GVE，结点v的介数()BCv按如下计算：1.对于每对结点(,)st，计算它们之间所有的最短路径；2.对于每对结点(,)st，通过判断，求出它在最短路径上的部分；33.对于每对结点(,)st求出的部分进行累加。绝对介数中心度以数学形式表达为()()stBsvtVstvCv其中，st是s到t的最短路径数，()stv是从s到t的最短路径中经过结点v的数量，它可以除以不包括结点v的结点对数量，对于有向图是(1)(2)nn，对于无向图是(1)(2)/2nn）来归一化，就得到了相对介数中心度。在Email网络中，介数中心度反映了节点控制其他点之间交往关系的能力。如果有很多节点之间的最短路径通过这个节点，说明这个节点是很重要的，是连接网络中其他节点的重要环节之一。2.2.4紧密中心度紧密中心度(closenesscentrality)描述的是一个节点与图中其他所有点之间距离的远近，如果该点与图中其他所有点之间的距离都很短，则说明该点与图中其他所有点都很“接近”，也就是说该点的紧密中心度很高。接近中心度刻画了一个点摆脱图中其他点控制的能力，如果网络中的一个行动者在于其他行动者交往过程中较少依赖于其他行动者，则此行动者拥有较高的接近中心度。接近中心度分为绝对接近中心度和相对接近中心度。相对中心度被定义为结点v到其他可达结点的平均测地距离\(,)1GtVvdvtn式中2n，(,)Gdvt是从v出发在网络中连通部分V的大小。紧密度可以看做从给定结点传播信息到网络中其他可达结点时间长短的度量。定义紧密度为这一量的倒数，结点v的紧密度()CCv是到其他所有结点V的测地距离和的倒数\1(,)CGtVvCdvt。2.2.5特征向量中心度特征向量中心度是网络中一个结点重要性的度量。网络中每个结点都有一个相对指数值，这个值是基于原则——高指数结点的连接对一个结点的贡献度比低指数结点的贡献度高。可以利用邻接矩阵来寻找特征向量的中心性。令ix为第i4个结点的（指数）值，,ijA为网络的邻接矩阵。当第i个结点是第j个结点的邻结点时，,1ijA，或者相反，,0ijA。一般来说，正如同随机矩阵A的每一项可以是表示连接强度的实数。对于第i个结点，中心性指数与所有连接它的结点的指数和成正比，有()111NijijjjMijxxAx。式中，()Mi是连接到i结点的结点集合，N是总结点数，是常数。2.3数学模型的建立和求解本题建立基于中心度指标的网络核心成员挖掘模型。本题采用邻接矩阵分析结点的中心度，进而分析人物在整个体系中地位的关键性。中心性分为点度中心度(DegreeCentrality)、介数中心度(BetweennessCentrality)、紧密中心度(ClosenessCentrality)和特征向量中心度(EigenvectorCentrality)。方法一所给的矩阵中的通信次数实际上反映了两个节点之间的联系的紧密程度，可以视为一个带权值的网络路径，那么联系次数越多，代表两个节点之间的距离越短，直观上来说关系越密切。那么这时我们所得的信息矩阵就可以处理成为距离矩阵，满足介数中心度和紧密中心度中所需要的两个节点之间的“距离”这个量，进而我们进行三度的计算。方法二中给出的矩阵显然要进行一定的压缩，否则计算量过大，效率低下。字符串搜索比对方法。首先进行人名的识别和分割，发现第一次分割正好是2307个人，说明这样的划分很可能就是正确的。经过分割以后的人名表，由人为判断存在一些简称、重名、中间名(middlename)等现象，但是大多数都是正规的姓名格式，所以我们手工进行了一些合并：1.去除矩阵的稀疏部分；2.只有名和同名含姓的合并；获得了较小矩阵后，再进行同方法1的处理。两种方法中，三个中心度指标都可以通过将矩阵输入mathematica9.0计算得出。首先可以利用Mathematica9.0画出网络的0-1图如图1，直观上感受150位高管之间的联系，如图所示，我们可以轻易排除图下方一些孤立的节点，尤其是两对孤立节点，他们的相关度也非常高，会对后来的相关度排序造成影响，故首先删去。而重要人物一定处于图的中心，三度应该都是比较高的。这一点也可以通过Ucinet的动态显示的功能判断。如图2，5图1150为高管之间联系的0-1矩阵图图2Ucinet中的动态分析法对于数据1，由于矩阵比较小，可以直接计算出结果。如下我们可以看到三个中心度的前10名排名中有一些人重复出现，显然是重要人物，而有的只有个别指标比较出众可能不是十分重要的人物。表1介数中心度排名前十编号姓名归一化介数中心度94Presto-k1.00063Lavorato-j0.97032Forney-j0.78156Kaminski-v0.76085Neal-s0.573139Watson-k0.56041Grigsby-m0.539146Williams-w30.537643Haedicke-m0.4802Arnold-j0.457表2中心度排名前十编号姓名归一化紧密中心度63lavorato-j1.00023delainey-d0.9982arnold-j0.996142whalley-l0.975138ward-k0.97480mclaughlin-e0.9691allen-p0.9688beck-s0.965141whalley-g0.96094presto-k0.959表3点度中心度排名前十编号姓名归一化点度中心度63lavorato-j1.00041grigsby-m0.7732arnold-j0.72743haedicke-m0.68285neal-s0.68223delainey-d0.6361allen-p0.63661kitchen-l0.63690perlingiere-d0.591109sanders-r0.591可见重要人物都会在某一项指标上比较突出，三项加权排名后能够得到重要人物。他们的名字和职位如下，可见该模型对人物重要性的挖掘比较准确有效。表4编号姓名职位1JohnLavoratoCE