Modeling of Complex Systems: Mining Suspicious Tiny SubNetworks in a Massive Social Network

SOW - Mining Suspicious Tiny Sub-Networks in a Massive Social Network Huan Liu, CIDSE, Arizona State University Finding a 30-Person Karate Club in the 30 Million-Person Network of social media is a remarkably difficult problem. Given the power-law distributions observed in social media, these 30-person karate clubs are by their nature located in the long tail [Arga09]. The ensued computational challenges include: (1) it is impractical to exhaustively search for these small groups, and (2) these small groups are often disconnected in terms of explicit friendship links. Hence, existing computational methods are not adequate to finding such tiny groups in a massive network. Social theories must be leveraged and developed with novel computational methods to meet the challenges. An increasing number of people use social media as an integrated and important means to conduct a great range of social activities such as commenting, following, bookmarking, tagging, etc. Therefore, many users are not only consumers, but also producers of social data, and particularly so in small groups. Given the nature of social media, the online activities of members of disconnected small groups strengthen their relationships through various ties, in the meantime producing additional information social media sites to enhance social networking services. We propose to combine our complementary expertise in data mining and social computing and social theories in this collaborative research to efficiently find disconnected small groups. Our proposed methodology addresses the challenging problem in two integrated approaches assisted with social theories and research on weak ties: (a) among many normal small groups, we investigate if we can find some anomalous groups that can sufficiently reduce the search space for us to find karate clubs of our interest; and (b) if we are given some karate club profiles of interest, we study whether we can find similar groups. We will further research the complementary properties of the two approaches in combination of weak tie research, develop novel metrics of quantification and evaluation, and show how the proposed approaches and metrics to be developed can efficiently handle the computational challenges. ASU will collaboratively work with UIUC on the following 1. Employing social media meta-data for finding small groups with similar group profiles: Karate groups are very likely not directly connected. Using meta-data such as tag networks may help to find these small groups in a massive network. Known suspicious groups or individuals can be used as seeds to finding indirect links among those by integrated search in social media metadata. 2. Understanding the roles of weak ties in finding Karate clubs. Weak social ties are deemed responsible for the structure of social networks in society and the transmission of information through these networks. After we find Karate clubs, we will further investigate the role of weak ties. We inquire whether normal and anomalous small groups have their distinct weak tie patterns in terms of classic and novel metrics of quantification and evaluation, and question if we can connect dots of certain Karate clubs via weak ties. 3. We will meet with UIUC group regularly, share and exchange findings and encountered issues, and write and prepare technical reports and progress reports collaboratively. We will explore social and computational theories, systematically study state-of-the-art methodologies, and develop scalable and effective methods to finding Karate clubs in social media networks of million nodes.