This patent application is assigned to
The following quote was obtained by the news editors from the background information supplied by the inventors: "The invention disclosed and claimed herein generally pertains to a method and apparatus for computing information pertaining to nodes of a weighted directed graph, such as a large social network graph. More particularly, the invention pertains to efficient computation of egonets in graphs of these types.
"A weighted directed graph generally comprises a number of nodes, and further comprises weighted edges that each extends from one of the nodes to another node. A weighted directed graph such as a social network can have a very large number of nodes, which may be on the order of millions or even billions of nodes. Also, social networks can have very important roles in fields exemplified by but not limited to healthcare, financial activities and crime prevention. It is therefore desirable to have tools available for processing graphs of these types with a high level of efficiency, in order to access and use important information contained in such graphs.
"A weighted directed graph as described above comprises a number of neighboring subgraphs, which are referred to as egonets. Computing respective egonets of a large social network can be a very important activity, such as to find or discover anomalies. However, currently used solutions typically compute the egonets one at a time. These approaches tend to be very tedious and time-consuming, particularly when used for large graphs as referred to above."
In addition to the background information obtained for this patent application, VerticalNews journalists also obtained the inventors' summary information for this patent application: "Embodiments of the invention provide an algorithm for computing in parallel the neighbor subgraph, or egonet, of each node in a directed weighted graph. Embodiments also can compute a significant number of characteristic features for each egonet. In one embodiment, a method is provided for computing specified information pertaining to respective nodes of a weighted directed graph, wherein the graph comprises multiple nodes and edges, each edge extending between two nodes and having a weight. The method includes the step of selectively processing the edges to generate a forward edge and a reverse edge that both correspond to each edge, wherein the forward edge and reverse edge corresponding to a given edge both extend between the same two nodes as the given edge. The method further includes selectively processing forward edges and reverse edges to generate multiple indirect edges, wherein each indirect edge comprises two edge components, and has two ends respectively associated with different nodes. The method includes the further step of specifying one node associated with each forward edge, one node associated with each reverse edge, and one node associated with each indirect edge to be the key node of its respective associated edge. All the forward, reverse and indirect edges that have the same particular node as their respective key nodes are placed into a group, and are then selectively processed to provide specified information pertaining to a particular egonet of the graph, wherein the particular node is the egonode of that particular egonet.
BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS
"FIG. 1 is a schematic diagram showing an egonet of a directed weighted graph, wherein information pertaining to features of the egonet can be computed by an embodiment of the invention.
"FIG. 2 is a schematic diagram illustrating features and information provided for the egonet of FIG. 1 by an embodiment of the invention.
"FIG. 3 is a simplified block diagram showing components that may be used to carry out map and reduce functions, in order to implement an embodiment of the invention.
"FIGS. 4-7 are schematic diagrams illustrating the construction and use of forward, reverse and indirect edges, to compute characteristics or features of an egonet in accordance with an embodiment of the invention.
"FIG. 8 is a flowchart showing steps for a method comprising an embodiment of the invention.
"FIG. 9 is a schematic diagram illustrating direct and indirect edges provided by an embodiment of the invention for a 2nd-degree egonet computation.
"FIG. 10 is a block diagram showing a network of data processing systems in which an embodiment of the invention may be implemented.
"FIG. 11 is a block diagram showing a computer or data processing system that may be used in implementing embodiments of the invention."
URL and more information on this patent application, see: Rosu,
Keywords for this news article include: Information Technology, Information and Data Processing,
Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC
Most Popular Stories
- Chinese May Have Spotted Malaysia Airlines Debris
- Why Buffett Bets Big on Green Energy
- 3 Shot Dead in Venezuela Unrest
- Better Pay Means Bigger Profits: Strategist
- Banks Buying Little From Minority Firms: Study
- Several Texas Cities Top Job Search List
- G7 Presses Russia to Pull Troops Out of Crimea
- Wall Street Rally Heads Off 3rd Day of Decline
- Senate Committee OKs Bill to Sanction Russia
- Obama's 'Between Two Ferns' Appearance Has Conservatives Upset