We propose new characterizations of social influence, which quantify both the transient and the steady-state propagation of beliefs across society. These characterizations are used to optimally choose a desired number of agents in a social network to serve as social leaders with maximal social impact. We then consider a framework for optimally creating new social links subject to resource constraints, in order to improve the influence of designated agents or social leaders. We show that the formulated optimization problems are convex with respect to the individual elements of the optimization variables. This motivates the use of the coordinate descent method, a simple but efficient algorithm well-suited to large-scale optimization problems. Finally, using demonstrative examples, we compare the ability of our proposed characterizations of social influence in identifying the most influential agents with that of other measures of influence developed in the social networks literature.