Power Graph Greedy Algorithm
The power graph greedy algorithm relies on two simple steps to perform the decomposition:
The first step identifies candidate power nodes through a hierarchical clustering of the nodes in the network based on the similarity of their neighboring nodes. The similarity of two sets of neighbors is taken as the Jaccard index of the two sets.
The second step performs a greedy search for possible power edges between candidate power nodes. Power edges abstracting the most edges in the original network are added first to the power graph. Thus bicliques, cliques and stars are incrementally replaced with power edges, until all remaining single edges are also added. Candidate power nodes that are not the end point of any power edge are ignored.
Read more about this topic: Power Graph Analysis
Famous quotes containing the words power, graph and/or greedy:
“But the nature of our civilized minds is so detached from the senses, even in the vulgar, by abstractions corresponding to all the abstract terms our languages abound in, and so refined by the art of writing, and as it were spiritualized by the use of numbers, because even the vulgar know how to count and reckon, that it is naturally beyond our power to form the vast image of this mistress called “Sympathetic Nature.””
—Giambattista Vico (1688–1744)
“When producers want to know what the public wants, they graph it as curves. When they want to tell the public what to get, they say it in curves.”
—Marshall McLuhan (1911–1980)
“Such is the end of all who are greedy for gain; it takes away the life of its possessors.”
—Bible: Hebrew, Proverbs 1:19.