The current "Big Data" boom coincides with the realization that data entities across systems are not independent. In order to allow realistic discovery in many domains like natural sciences, on-line social systems and media, transportation and economics, one needs to consider their underlying networks. Graphs and corresponding mining and analysis algorithms provide a powerful framework for analysis of big networked data. All graph application domains, however, include more facets than simply binary relations among entities. Networks may (i) evolve over time; (ii) incorporate multiple layers; and (iii) exhibit special node/edge semantics such as collaboration compatibility, opposition/agreement and others. While, taking such rich information into account allows for more realistic analysis and mining for characteristic domain phenomena, it also introduces novel computational challenges.

In this thesis, I develop methods for mining and search in large graphs that observe temporal evolution of edge/node values, multi-type edges or special semantics of tie strength. In the area of temporal networks, I introduce the problem of the heaviest dynamic subgraph and corresponding mining methods that scale to large real world instances. I consider composite networks for function prediction in biology and multi-criteria proximity search in social and information multi-mode networks. I employ signed and labeled relations to study agreement and disagreement and for mining group effectiveness in collaboration networks. The urgent need to incorporate such rich information in graph analysis and mining is the commonality among the above three directions in my thesis. My primary focus in every chapter is on algorithms that scale to real-world networks and simultaneously maintain high quality of the obtained results.

Overall, I propose core mining and search algorithms that extend the current state of the art in computer science research. The utility of rich network information such as time, multi-modality and special semantics acts as a unifying theme in all chapters and across the various applications domains including, but not limited to, bioinformatics, communication graphs, social networks and media, collaboration and effectiveness of teams, sensor networks, and transportation networks.