The articles in this special issue report on up-to-date advances in the broad area of information processing over graphs. Due to the highly cross-disciplinary nature of complex networks, the technical articles in this April 2013 issue of the IEEE Journal of Selected Topics in Signal Processing are coupled with valuable tutorial articles that appear in a second special issue, organized by the same Guest Editors, and which is published as the May 2013 issue of the IEEE Signal Processing Magazine. The survey articles in the magazine are meant to introduce readers to the main tools and concepts, while the more focused technical articles in J-STSP cover state-of-the-art results. Through this combination of tutorial and technical articles in both journals, readers will become better acquainted with the challenges and opportunities that the broader field of network science has to offer across the domains of information sciences, system science, computer science, social sciences,machine learning, and optimization theory. Complex networks represent a typical paradigm that helps demonstrate well how barriers among seemingly different disciplines are becoming more transparent.