Search results


Title

Edge impact in graphs and social network matrix completion

Creator

Ross, Dennis

Date

2016

Collection

Electronic Theses & Dissertations

Description

Every graph G can be associated with many wellknown 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 Pimpact 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 distanceimpact in trees is...
Show moreEvery graph G can be associated with many wellknown 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 Pimpact 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 distanceimpact 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 coldstart vertices using a subspace sharing method that decouples matrix completion and side information transduction is presented. This method is extended to predict ratings in useritem recommender systems where both may be coldstart.
Show less