Back to search

Michigan State University

Edge impact in graphs and social network matrix completion

Abstract

dc:description

Every graph G can be associated with many well-known invariant properties along with their corresponding values. A framework is proposed to measure the change in any particular invariant upon addition of a new edge $e$ in the resulting graph G+e. In graphs, the P-impact of an edge e is the `magnitude' of the difference between the values of the invariant P in graphs G+e from G. Several famous invariants are explored and a proof towards optimal edge addition for distance-impact in trees is given. A natural application to measuring the impact of edge addition to a graph is that of link prediction. An efficient algorithm for link prediction even with cold-start vertices using a subspace sharing method that decouples matrix completion and side information transduction is presented. This method is extended to predict ratings in user-item recommender systems where both may be cold-start.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Ross, Dennis
Contributors dc:contributor
  • Esfahanian, Abdol-Hossein
  • Tan, Pang-Ning
  • Xing, Guoliang
  • Nejadhashemi, Amir Pouyan

Subjects

dc:subject × 3

Rights

dc:rights
Statement dc:rights
  • In Copyright
Language dc:language
English

Identifiers

dc:identifier.*
Identifier
etd:3985
isbn:9781339828657
isbn:1339828650
oclc:961288566
umi:10124766
local:Ross_grad.msu_0128D_14558

Chain of custody

source
Harvested from
Michigan State University
Base URL
d.lib.msu.edu/oai
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Ross, Dennis. Edge impact in graphs and social network matrix completion. 2016. https://doi.org/doi:10.25335/cw39-hy43