Link discovery in very large graphs by constructive induction using genetic programming

K-REx Repository

Show simple item record Weninger, Timothy Edwards 2008-12-18T22:34:12Z 2008-12-18T22:34:12Z 2008-12-18T22:34:12Z
dc.description.abstract This thesis discusses the background and methodologies necessary for constructing features in order to discover hidden links in relational data. Specifically, we consider the problems of predicting, classifying and annotating friends relations in friends networks, based upon features constructed from network structure and user profile data. I first document a data model for the blog service LiveJournal, and define a set of machine learning problems such as predicting existing links and estimating inter-pair distance. Next, I explain how the problem of classifying a user pair in a social networks, as directly connected or not, poses the problem of selecting and constructing relevant features. In order to construct these features, a genetic programming approach is used to construct multiple symbol trees with base features as their leaves; in this manner, the genetic program selects and constructs features that many not have been considered, but possess better predictive properties than the base features. In order to extract certain graph features from the relatively large social network, a new shortest path search algorithm is presented which computes and operates on a Euclidean embedding of the network. Finally, I present classification results and discuss the properties of the frequently constructed features in order to gain insight on hidden relations that exists in this domain. en
dc.description.sponsorship Defense Intelligence Agency; Department of Homeland Security; National Agriculture Biosecurity Center en
dc.language.iso en_US en
dc.publisher Kansas State University en
dc.subject Link Mining en
dc.subject Graph Theory en
dc.subject Machine Learning en
dc.subject Evolutionary Computation en
dc.title Link discovery in very large graphs by constructive induction using genetic programming en
dc.type Thesis en Master of Science en
dc.description.level Masters en
dc.description.department Department of Computing and Information Sciences en
dc.description.advisor William H. Hsu en
dc.subject.umi Artificial Intelligence (0800) en
dc.subject.umi Computer Science (0984) en 2008 en December en

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search K-REx

Advanced Search


My Account

Center for the

Advancement of Digital


118 Hale Library

Manhattan KS 66506

(785) 532-7444