Large graph mining methods: различия между версиями

'''Diffusion neighborhood-based computations''' can be thought of as a softer or fuzzy version of geodesic neighborhood-based computations. The use of graph diffusions in graph mining is typically a formalization of the following idea: importance flows from a source node along edges of the graph to target nodes. The mechanics of how the diffusion behaves on an edge of the graph determines the particular type of diffusion. Well known examples are: the PageRank diffusion, the Katz diffusion, the heat kernel diffusion, the truncated random walk diffusion. These methods can be used to answer questions such as “What does the region of this graph look like around this specific object?” They are also easy to scale to massive graphs because they do not need to explore the entire graph. For example, random walks with restart are an instance of this idea. One should think of running these diffusion neighborhoods on only <math> O(\log n)</math> or <math> O(\sqrt n)</math> of the nodes instead of on all nodes.

'''Mining with generalized matrix-vector products''' is one of the most flexible and scalable ways to mine large graphs. As the name suggests, these methods emerge from a generalized notion of a matrix-vector product on generalizations of the adjacency matrix of a graph. In a more general sense, a matrix-vector product can be seen as a special case of the following computational primitive: update vertex data based on a function of its neighbors data. The standard matrix-vector product uses summation as the function. Iterative sequences of these operations, with different functions, compute connected components, single-source shortest paths, label propagation, effective diameters, and distance histograms. Operations such as minimum spanning trees, maximum weight matchings, and message passing methods fit into the same framework as well. All of these methods and algorithms apply to batch systems rather than online systems.