People often adopt improved behaviors, products, or ideas through the influence of friends.  One way to spread such positive elements through society is to identify those most influential agents, those that cause the maximum spread, and initiate the spread by seeding them. However, this strategy has a key difficulty: finding these influential seed nodes. This is difficult even if both the network structure and the way how the spread goes are known. In social networks, cascades model the phenomena that agents receive certain information, adopt certain products, or take up certain political opinions from their neighbors due to their influence. In the influence maximization problem, a central planner is given a graph and a limited budget k, and he needs to pick k seeds such that the expected total number of infected vertices in the graph at the end of the cascade is maximized. This problem plays a central role in viral marketing, outbreak detection, rumor controls, etc.

This talk will focus on computational complexity, approximability and algorithm design aspects of the influence maximization problem, with both submodular and nonsubmodular cascade models. Firstly, I will present my recent results about the algorithmic complexity of submodular influence maximization, which are breakthrough in understanding the approximability of submodular influence maximization during the last 15 years. Secondly, I will present a new sociologically founded nonsubmodular cascade model that I proposed and show that how the seeding strategy for nonsubmodular cascade models is fundamentally different compared to submodular cascade models.

Finally, I will survey some of my other work, especially, my work in the fair division problem.