Social Network Archetypes and Vertex Similarity, Graph Matching and the Generalized Eigenvalue Problem

Details Social Network Archetypes and Vertex Similarity, Graph Matching and the Generalized Eigenvalue Problem Social Network Archetypes and Vertex Similarity, Graph Matching and the Generalized Eigenvalue Problem

2011-10-12

arxiv.org/abs/1110.2813v1

Computer Science

Social and Information Networks

13 papers, 5 figures

Scientific paper

Vertex similarity and graph matching are two significant problems with numerous important applications in different scientific fields, such as data mining, social network analysis, computer vision, biology, chemistry and many more. A key problem towards the design of successful algorithms is finding a good definition of similarity. In this work we provide novel perspectives on both problems. Inspired by the concept of archetypal analysis introduced by Cutler and Breiman \cite{cutler}, we propose for the vertex similarity problem a geometric optimization problem which allows us to express each vertex uniquely as a convex combination of few extreme types of vertices. We use this mapping of vertices to vectors of mixture coefficients to define vertex similarity. Furthermore, our method has the advantage of supporting efficiently several types of queries such as "which other vertices are most similar to this vertex?" by the use of the appropriate data structures. With respect to the graph matching problem between two graphs $G,H$, we propose the generalized condition number $\kappa(L_G,L_H)$ of the Laplacian matrix representations of $G,H$ --a quantity widely used in numerical analysis-- as a measure of graph similarity. We show that this objective has a solid theoretical basis and propose a deterministic and a randomized graph alignment algorithm. We validate our algorithms on both synthetic and real data. We present promising and interesting findings in our experimental results. Furthermore, we discuss in detail several aspects of our work and propose several research directions.

Affiliated with

Also associated with

No associations

Rating

Social Network Archetypes and Vertex Similarity, Graph Matching and the Generalized Eigenvalue Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Social Network Archetypes and Vertex Similarity, Graph Matching and the Generalized Eigenvalue Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Social Network Archetypes and Vertex Similarity, Graph Matching and the Generalized Eigenvalue Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-498376