Understanding dynamics and resource allocation in social networks

textWidespread popularity of various online social networks has attracted significant attention of the research community. Research interest in social networks are broadly divided into two categories: understanding the social or human network dynamics and harnessing the social network dynamics to gain economic, business or political advantage using minimal resource. These two research directions fuel each other. Better understanding offers better resource utilization/allocation in harnessing the network and the need for better resource utilization/allocation drives the fundamental research in understanding human networks. This thesis considers important problems in both directions as well as at their intersection. We first study opinion dynamics in social networks. We propose a new stochastic dynamics which generalizes two widely used and complementary models of opinion dynamics, graph-based linear dynamics and bounded confidence dynamics into a single stochastic dynamics. We analytically study the conditions under which such dynamics result in reconciliation or some sort of consensus. Our findings relate well to observed behaviors of societies. The next problem that we consider is related to designing personalized/targeted advertisements or campaigns for social network users. Currently viral marketing or campaigning rely only on the structure of the friendship graph. In reality friends may have different opinions on different topics or issues. It is understood that if opinions regarding a topic were known one could design better targeted campaigns. We propose algorithms which can infer opinions of people by observing their interactions regarding a topic or an issue. As data gathering and computation requires resources, our algorithm is designed to work with fewer such resources for a broad class of social networks and interaction patterns. A recent trend among different businesses is to work with social software providers (e.g., Lithium, Salesforce.com) to engage consumers online and often involve the online crowd directly in developing and running business ideas. This trend, popularly known as crowdsourcing uses human cloud to do jobs that cannot be done by machines. Crowdsourcing has been successfully used to do simple human tasks (Amazon Mechanical Turk), scientific research (fold.it), freelance software development(oDesk) as well as in impacting the lives of people in poverty (Samasource). Many big business houses use crowdsourcing, e.g., Microsoft, Samsung, Intel etc., IBM harness its employee pool using internal crowdsourcing. As employing humans (a.k.a. agents) for jobs, and especially for skilled jobs (like software development, scientific studies) is costly, an efficient job to agent allocation is key to the success of crowdsourcing. Motivated by this, in the last part of the thesis we study efficient resource allocation in skill-based crowdsourcing platforms.Electrical and Computer Engineerin