Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
Many machine learning algorithms use graphs to model relations between data points. One of the main objects of interest for such algorithms is the distance between vertices. There are several distance functions defined between graph vertices, each reflecting different properties of the underlying graph. The first part of this thesis characterizes properties of global distance functions in graphs: • Shortest path distance: The behavior of the shortest path distance depends on how we construct our graph from the data points. I show that in unweighted k-nearest neighbor graphs, the shortest path distance converges to an unpleasant distance function whose properties are detrimental to some machine learning problems. • p-resistance distance: The p-resistance distance is a generalization of the resistance distance and contains several other distances as its special cases. I study the convergence of the p-resistance distance in large geometric graphs and show that an interesting phase transition takes place. There exist two critical thresholds p* and p** such that if p < p*, then the p-resistance depends on meaningful global properties of the graph, whereas if p > p**, it only depends on trivial local quantities and does not convey any useful information. The second part of this thesis deals with local distances in graphs. Local clustering and friend recommendation are the topics covered in this part. • Local clustering is the task of finding a highly connected cluster around a vertex of interest. I propose a new random walk model for local clustering, consisting of several \"agents\" connected by ropes. All agents move independently but their distances are constrained by the ropes between them. The main insight is that for several agents it is harder to simultaneously travel over the bottleneck of a graph than for just one agent. • Local distances are used for recommending new friends in social networks. Here, I propose a new distance between members of the network that exploits the temporal data in the ...