《自动社交网络图挖掘和可视化的制作方法》由会员分享，可在线阅读，更多相关《自动社交网络图挖掘和可视化的制作方法（5页珍藏版）》请在金锄头文库上搜索。
1、自动社交网络图挖掘和可视化的制作方法专利名称：自动社交网络图挖掘和可视化的制作方法自动社交网络图挖掘和可视化许多社交网络应用近年来在因特网上上线，以允许人们在社交上以及职业上连接。通常，这样的社交网络应用要求用户创建用户标识(ID)和口令并标识其朋友以便创建简档。然而，万维网或因特网上的诸如新闻站点、博客、评论等许多网页描述人们和其他实体的社交活动，尽管这些信息没有列在社交网络应用站点上。另外，尽管存在许多社交网络应用，但没有多少方式来容易地确定和查看人们和其他实体之间的社交连接或关系。概述提供本概述是为了以简化的形式介绍将在以下详细描述中进一步描述的一些概念。本概述并不旨在标识出所要求保护的
2、主题的关键特征或必要特征，也不旨在用于限定所要求保护的主题的范围。此处描述的自动社交网络图挖掘和可视化技术从一般(不必是社交应用专用的)网页挖掘社交连接，并允许对社交网络关系进行可视化。更具体而言，在一个实施例中，该自动社交网络图挖掘和可视化技术对实体的社交网络图进行自动挖掘和布局。实体可以是例如人、组织或甚至关键词。该技术使用一个或多个网页上一实体的名称和相关实体的名称之间的距离来确定各实体之间的连接以及这些连接的强度。在挖掘过程中，输入是一般的网页。人或其他实体的名称以及他们之间的社交连接被自动提取和综合。对于每一实体名称，其社交网络图被定义为在一个或多个网页中连接到该实体名称的名称集和从
3、该Web中标识的这些连接的实体名称之间的社交连接集的结合。这些社交连接可由关系排序过程来加权。在一个实施例中，该社交网络图挖掘和可视化技术可使用一布局过程来生成围绕人或其他实体的名称的二维(2-D)社交网络图。在该技术的一个实施例中，该布局通过使用力指向模型和能量缩减过程来自动生成。在该布局中，社交连接权重由其两个端点之间的距离来表示。该距离越短，则该连接权重越大。同样，在一个实施例中，该布局过程聚集彼此紧密连接在一起的人或其他实体的名称。参考以下描述、所附权利要求书以及附图，将更好地理解本公开的具体特征、方面和优点，附图中图I是用于采用此处描述的自动社交网络图挖掘和可视化技术的一个示例性实施
4、例的示例性体系结构。图2描绘了用于采用自动社交网络图挖掘和可视化技术的示例性过程的流程图。图3描绘了用于根据自动社交网络图挖掘和可视化技术的一个示例性实施例来创建社交网络图的示例性过程的流程图。图4描绘了由自动社交网络图挖掘和可视化技术的一个示例性实施例创建的示例性社交网络图。图5描绘了在自动社交网络图挖掘和可视化技术的一个示例性实施例中采用的图形用户界面。图6是可用于实现自动社交网络图挖掘和可视化技术的示例性计算设备的示意图。详细描述在对自动社交网络图挖掘和可视化技术的以下描述中，对附图作出参考，附图形成了该描述的一部分，且作为可实现此处所述的自动社交网络图挖掘和可视化技术的说明性示例示出。
5、可以理解，可以利用其它实施例，并且可以作出结构上的改变而不背离所要求保护的主题的范围。1. O自动社夺网络图校掘和可视化抟术以下各节提供了自动社交网络图挖掘和可视化技术的综述，以及用于采用该技术的示例性体系结构、过程和用户界面。1. 1抟术综沭社交网络近来受到了更多的关注。如Facebook和Twitter这样的社交网络应用和服务允许用户增长其自己的私人社交网络。然而，因特网实际上包含了隐含于一般网页中的文本中的公共社交网络。例如，描述社交活动的网页提供了这些网页上所提到的人或实体之间的隐含社交连接。这些公共的隐含社交连接可被视为巨大的社交网络图。几乎没有进行任何工作来从并非为社交网络应用特别
6、设计的网页中自动标识并呈现人和其他实体之间的社交连接。在一个实施例中，该自动社交网络图挖掘和可视化技术从一般的网页中自动标识社交网络连接，并以2-D布局提供允许查看者容易地标识该图中的人或实体之间的连接以及这些连接的强度的社交网络图。在一个实施例中，该技术创建2-D可视化布局，该布局提供了特定实体的社交网络图为一组基于该实体和其他实体之间的连接和连接强度以径向布局排列的顶点(名称)和边(社交连接)。该社交图的所有者(例如，为其生成该图的实体)被置于中心。采用上述挖掘过程和布局过程，来自web的社交网络图被自动生成并可视化。1. 2示例件体系结构图1提供了用于采用自动社交网络图挖掘和可视化技术的
7、一个实施例的示例性体系结构100。如图I所示，体系结构100采用社交网络图挖掘和可视化模块102，该模块驻留在将参考图6更详细讨论的计算设备600上。社交网络图挖掘和可视化模块102用于挖掘社交网络图104并在显示器106上将其呈现给用户，用户108可经由用户界面110来操纵该社交网络图。网页112被输入到社交网络图挖掘和可视化模块102中。网页视觉解析器114将来自所输入的每一网页的网页内容解析成信息块116。信息块116被输入到名称提取器118中，后者从信息块中识别实体名称。这些实体可以是例如人、组织或关键词。标记了实体名称的信息块120被输入到社交连接排序器122中，后者确定所标记的信息
8、块116中所标识的实体之间的一个或多个连接并对这些连接排序。社交连接排序器122还标识连接的强度并对其分配权重。用于确定排序的一个示例性过程将在下文中更详细讨论。社交连接排序器122输出已排序的实体名称及其连接权重124。这些连接权重124被输入到社交连接综合器126中，后者综合所有已排序的实体名称及其连接权重124，并使用力指向模型创建社交网络图104并在显示器106上输出该图。一旦在显示器106上显示了社交网络图104的各部分，用户108就能经由用户界面110操纵该社交网络图104来示出其其他部分，这将在下文中更详细讨论。I. 3.自动社交网络图挖掘和可视化技术所采用的示例性过程以下各段提
9、供了对用于采用自动社交网络图挖掘和可视 化技术的示例性过程的描述。应当理解，在某些情况下，动作的次序可以互换，并且在某些情况下，部分动作甚至可被省略。I. 3. I自动社夺网络图校掘用于采用自动社交网络图挖掘和可视化技术的一个实施例的过程的高级流程图在图2中示出。该技术的该实施例从一般的网页中挖掘社交连接及其强度。如图2所示，在框202，将这些网页输入到该过程中。这些输入的网页可例如通过web爬行器爬行因特网来找到。每一所输入的网页的内容被解析成信息块，如框204所示。例如，标识文本块或其他邻接数据块的视觉解析器可用于解析网页的内容。可使用各种常规技术来标识并解析该文本或其他邻接数据块。然后标
10、识在信息块中找到的人或实体的名称，如框206所示。例如，这可由常规的名称寻找器来完成。此处，常规名称寻找器指的是能够从信息块中自动寻找实体名称的任何计算机算法。如框208所示，然后对信息块中的实体名称之间的社交连接排序。在该技术的一个实施例中，排序考虑了名称的位置以及信息块中的环绕文本(例如，名称的位置以及文本中将名称隔开的特定距离或单词数)。两个名称彼此越靠近，则认为连接的强度越强。关于该技术的一个实施例所采用的排序过程的细节将在下文中给出。然后对来自所有信息块的已排序的社交连接进行综合以确定在网页上找到的实体之间的社交连接的强度，如框210所示。在社交网络图挖掘和可视化技术的一个实施例中，
11、该综合在确定对每一信息块找到的连接的强度时，除了信息块中的名称的接近度之外，还考虑了在网页上找到同一名称集的频率。社交连接的强度然后可用于各种目的，如确定某人的朋友是谁，或用于对这些社交连接绘图以提供确定人或其他实体之间的社交连接强度的视觉帮助，如框212所示。I. 3. 2可视化社交连接图3提供了由自动社交网络图挖掘和可视化技术用来可视化社交连接的一个示例性过程300的流程图。在该技术的该实施例中，从一般的网页中提取的人/实体的名称之间的社交连接以2-D图的形式来表示，该2-D图具有一组表示名称的顶点，以及一组表示社交连接的边。使用力指向模型来表示该2-D图，并且使用能量最小化过程来充分优化
12、或增强该2-D图的布局。如框302所示，输入已排序社交连接的列表。将社交图的所有者(为其显示该图的人)置于该2D图的中心作为中心顶点，如框304所示。表示人或其他实体的名称、且具有到社交图的所有者的社交连接的顶点被置于中心顶点周围的不同轨道中(或基于排序置于该中心顶点周围的轨道中)，如框306所示。轨道的半径越短，则该轨道中的顶点与中心顶点之间的社交连接越强。为每一社交连接创建中心顶点周围的一条轨道，其中具有到该所有者的最强社交连接的顶点(实体)最接近该中心顶点。如框308所示，顶点然后可根据顶点之间的连通性被聚集到不同聚类中(例如，根据他们之间的连接以及将在下文中更详细描述的能量最小化过程来
13、聚集)。同一聚类中的顶点(例如，其之间具有多于一个连接的顶点)被彼此接近地放置。顶点聚类也被放置成使得顶点聚类不彼此重叠，如框310所示。如框312所示，然后使用力指向模型来充分优化2D图的布局的均一性。图4提供了由该技术的一个实施例产生的2D图布局400的一个示例。在社交网络图挖掘和可视化技术的该实施例中，力指向模型通过采用一组力和能量最小化过程将该布局充分优化为均一I)每两个顶点之间的排斥力402 (其一个示例在图4中示出)；2)沿着边的吸引力404 (例如，在顶点402之间的社交连接之间)；3)相邻轨道之间的排斥力406 ；以及4)被建模以隔离彼此之间没有连接的聚类的不可穿透边界408。
14、5)图中的每一对象，例如每一顶点、边、轨道和不可穿透边界，或者是径向/切向自由的，或者两个方向都是自由的，从而能够根据力指向模型的力来移动。因此，在每一顶点处在力指向模型中有四种不同的力沿着边的吸引力404 A(O) = .4 5+ca9Wm其中i，j表示第i个顶点和第j个顶点；d表示距离；0k表示第k条轨道；Um表示第m条不可穿透边界；(,2,3表示常量；表示线的正交角，其穿过顶点和中心顶点以及不可穿透边界；并且表示常量阈值。给定以上定义，一个顶点处的聚集力为hmm= fiihj)+TJ1HJ)+/AOk1)+Yj4(i,um)VMiJieaJWm当力在一个顶点处平衡时，该顶点处的聚集力为零
15、。因此，该技术寻求最小化所有顶点的聚集力的总和。布局算法然后寻找顶点的适当放置，其中放置=arg min Y Fj 可被认为是该布局的能量，因此该布局算法实际上缩减力模型的总能量。在 i该技术的一个实施例中，能量缩减过程以迭代的方式来执行。在每一次迭代中，每一顶点沿着聚集力的方向移动。该过程在能量收敛于特定水平时停止。更具体而言，当能量下降时，顶点的总位移也减小。该技术设置一常量阈值。当总位移小于该值时，迭代过程停止。在那时之前，顶点在每一次迭代中保持移动，即，其位置改变。I. 3. 3对社夺连梓棑序如先前所讨论的，社交网络图挖掘和可视化技术的某些实施例采用了排序过程来对实体之间的社交连接排序
16、。下节给出了关于在该技术的一个实施例中使用的排序过程的附加信息。该技术的一个实施例所采用的排序可描述如下。给定实体名称列表=(，. . . 和网页列表W= wQ, W1, . ,每一网页具有信息块B= bQ, b1； . . . ,如果Xi, 出现在一个信息块中，则信息块中这两个名称之间的关系权重被定义为Rb (xi； Xj) =Rd Rc其中Rd表示关系的距离度量，而R。表示关系的上下文度量。这两个度量的定义如下 d(xx.) lRd (Xi, X) ) 二 I-)Rc= (Xi, Xj) =1. OK (Xi, Xj) = TlkmK(XiXj) = kj A此处，(Kxi, Xj)表示信息块中Xi, Xj之间的字符距离。如果Xi, Xj不一起出现在信息块中，则d(Xi，Xj)是无穷的。S卩，Rd等于零。变量K(Xi，Xj)表示在该信息块中的两个名称之间发现的关系关键词集，如“妻子”、“朋友”等。变量km表示预定义关键词权重，km1.0。在一个
