The past decades have seen a fast-growing and dynamic trend of network science and its applications. From the Internet to Facebook, from telecommunications to power grids, from protein interactions to paper citations, networks are everywhere and the network paradigm is pervasive. Network analysis and mining has become an important tool for scientific research and industrial applications to diverse domains. For example, finding communities within social networks enables us to identify groups of densely connected customers who may share similar interests and behaviors and thus generate more effective recommender systems; investigating the supply-network topological structure and growth model improves the resilience of supply networks against disruptions; and modeling influence diffusion in social networks provides insights into viral marketing strategies. However, none of these tasks is trivial. In fact, community detection, resilience analysis, and influence-diffusion modeling are all important challenges in complex networks. My PhD research contributes to these endeavors by exploring the implicit knowledge of connectivity and proximity encoded in the network graph topology. Our research originated from an attempt to find communities in networks. After carefully examining real-life communities and the features and limitations of a set of widely-used centrality measures, we develop a simple but powerful reachability-based influence-diffusion model. Based upon this model, we propose a new influence centrality and a novel shared-influence-neighbor (SIN) similarity. The former differentiates the comprehensive influence significance more precisely, and the latter gives rise to a refined vertex-pair closeness metric. Then we develop an influence-guided spherical K-means (IGSK) algorithm for community detection. Further, we propose two novel influence-guided label propagation (IGLP) algorithms for finding hierarchical communities in complex networks. Experiments on both real-life networks and synthetic benchmarks demonstrate superior performance of our algorithms in both undirected/directed and unweighted/weighted networks. Another research topic we investigated is resilience analysis of supply networks. Supply networks play an important role in product distribution, and survivability is a critical concern in supply-network design and analysis. We exploit the resilience embedded in supply-network topology by exploring the multiple-path reachability of each demand node to other nodes, and propose a novel resilience metric. We also develop new supply-network growth mechanisms that reflect the heterogeneous roles of different types of units in supply networks. We incorporate them into two fundamental network topologies (random-graph topology and scale-free topology), and evaluate the resilience under random disruptions and targeted attacks using the new resilience metric. The experimental results verify the validity of our resilience metric and the effectiveness of our growth model. This research provides a generic framework and important insights into the construction of robust supply networks. Finally, we investigate activation-based influence-diffusion modeling for viral marketing. One of the fundamental problems in viral marketing is to find a small set of initial adopters who can trigger the largest further adoptions through word-of-mouth-based influence propagation in the network. We propose a novel multiple-path asynchronous threshold (MAT) model, in which we quantitatively measure influence and keep track of its diffusion and aggregation during the diffusion process. Our MAT model captures both direct and indirect influence, influence attenuation along diffusion paths, temporal influence decay, and individual diffusion dynamics. Our work is an important step toward a more realistic diffusion model. Further, we develop two effective and efficient heuristics (IV-Greedy and IV-Community) to tackle the influence-maximization problem. Our experiments on four real-life networks demonstrate their excellent performance in terms of both influence spread and efficiency. Our work provides preliminary but significant insights and implications for diffusion research and marketing practice.

The study of networks has seen a tremendous breed of researches due to the explosive spectrum of practical problems that involve networks as the access point. Those problems widely range from detecting functionally correlated proteins in biology to finding people to give discounts and gain maximum popularity of a product in economics. Thus, understanding and further being able to manipulate/control the development and evolution of the networks become critical tasks for network scientists. Despite the vast research effort putting towards these studies, the present state-of-the-arts largely either lack of high quality solutions or require excessive amount of time in real-world `Big Data' requirement. This research aims at affirmatively boosting the modern algorithmic efficiency to approach practical requirements. That is developing a ground-breaking class of algorithms that provide simultaneously both provably good solution qualities and low time and space complexities. Specifically, I target the important yet challenging problems in the three main areas: Information Diffusion: Analyzing and maximizing the influence in networks and extending results for different variations of the problems. Community Detection: Finding communities from multiple sources of information. Security and Privacy: Assessing organization vulnerability under targeted-cyber attacks via social networks.