The study of networks in general and social networks in particular, has intensified in recent years due in part to the interest in on-line social networks and the availability of large data sets of related objects. An area called network mining has emerged from the larger area of data mining, whose purpose is to extract hidden knowledge from large, linked data sets.

It is the purpose of this dissertation to study the relationships that develop in networks involving links, specifically the relationships between links and communities and between links and attributes. Understanding the alignment between communities and the links offers valuable insights into the roles that nodes play with respect to communities. It will also be shown that learning the alignment between links and attributes leads to improvements in link prediction and collective classification. Finally, studying the changes in the relationship of attributes to links over time has revealed information helpful for decisions that are made in processing network data.

During the course of this investigation, a number of tangible new algorithms and metrics have been discovered. First, a new metric is introduced that provides information about the number of communities to which a node belongs without having the actual community information. Combining this rawComm metric with the relative degree of a node allows community-based roles to be assigned to nodes. Next, a new framework is proposed that uses weights to align the attributes to the link structure. Two formulations of the framework are used for improving link prediction and collective classification techniques. It is also shown to be valuable in studying the dynamics of temporal networks.