Faculty Publications
Permanent URI for this communityhttps://idr.nitk.ac.in/handle/123456789/18736
Publications by NITK Faculty
Browse
10 results
Search Results
Item Dynamic structure for web graphs with extended functionalities(Association for Computing Machinery acmhelp@acm.org, 2016) Goyal, S.; Bindu, P.V.; Santhi Thilagam, P.S.The hyperlink structure of World Wide Web is modeled as a directed, dynamic, and huge web graph. Web graphs are analyzed for determining page rank, fighting web spam, detecting communities, and so on, by performing tasks such as clustering, classification, and reachability. These tasks involve operations such as graph navigation, checking link existence, and identifying active links, which demand scanning of entire graphs. Frequent scanning of very large graphs involves more I/O operations and memory overheads. To rectify these issues, several data structures have been proposed to represent graphs in a compact manner. Even though the problem of representing graphs has been actively studied in the literature, there has been much less focus on representation of dynamic graphs. In this paper, we propose Tree- Dictionary-Representation (TDR), a compressed graph representation that supports dynamic nature of graphs as well as the various graph operations. Our experimental study shows that this representation works efficiently with limited main memory use and provides fast traversal of edges. © 2016 ACM.Item Diffusion models and approaches for influence maximization in social networks(Institute of Electrical and Electronics Engineers Inc., 2016) Tejaswi, V.; Bindu, P.V.; Santhi Thilagam, P.S.Social Network Analysis (SNA) deals with studying the structure, relationship and other attributes of social networks, and provides solutions to real world problems. Influence maximization is one of the significant areas in SNA as it helps in finding influential entities in online social networks which can be used in marketing, election campaigns, outbreak detection, and so on. It deals with the problem of finding a subset of nodes called seeds such that it will eventually spread maximum influence in the network. This paper focuses on providing a complete survey on the influence maximization problem and covers three major aspects: i) different types of input required ii) influence propagation models that map the spread of influence in the network, and iii) the approximation algorithms suggested for seed set selection. We also provide the state of the art and describe the open problems in this domain. © 2016 IEEE.Item Deriving temporal trends in user preferences through short message strings(Institute of Electrical and Electronics Engineers Inc., 2016) Deb, S.; Mohan, S.; Venkatraman, P.; Bindu, P.V.; Santhi Thilagam, P.S.Short message strings are widely prevalent in the age of social networking. Taking Facebook as an example, a user may have many other users in his contact list. However, at any given time frame, the user interacts with only a small subset of these users. In this paper, we propose a recommender system that determines which users have common interests based on the content of the short message strings of different users. The system calculates the similarity between two users based on the contents of short message strings by the users over a certain time period. A similarity measure based on short message strings must be temporal study as the contents of the short messages vary rapidly over time. Experimental study is conducted in the Facebook domain using status updates of users. © 2016 IEEE.Item In-memory representations for mining big graphs(Institute of Electrical and Electronics Engineers Inc., 2017) Goyal, S.; Bindu, P.V.; Santhi Thilagam, P.S.Graphs are ubiquitous and are the best data structure for representing linked data because of their flexibility, scalability, and power to deal with complexity. Storing big graphs in graph databases leads to difficult computation and increased time complexity. The best alternative is to use inmemory representations such as compact data structures. They compress the graph sufficiently such that it can be stored in memory and can allow all the possible operations in compressed form itself. In this paper we discuss about five compression techniques: WebGraph, Re-pair, BFS, k2, and dk2. In addition, we compare them based on four parameters: compression ratio, supported functionalities, supported graph types, and dynamic support. The paper is concluded by bringing out the need to have a more advanced, dynamic, and versatile compression technique. © 2016 IEEE.Item Target specific influence maximization: An approach to maximize adoption in labeled social networks(Institute of Electrical and Electronics Engineers Inc., 2017) Tejaswi, V.; Bindu, P.V.; Santhi Thilagam, P.S.Influence maximization deals with finding a small set of nodes, called seed set, to be initially influenced such that they will eventually spread the influence to maximum number of users in the social network. This paper deals with a specialization of the basic problem called labeled influence maximization that identifies seeds that will maximize the influence spread among a specific set of target users identified by their attribute values. In a social setting, a large difference exists between awareness and adoption of an idea/product. This notion fits well in case of labeled influence maximization where any user can become 'aware' about a product whereas only specific users 'adopt' the product. This work considers the problem of labeled influence maximization by incorporating the difference between awareness and adoption. Due to the inherent difference in nature, characteristics, and interests of every user, the number of users who adopt a product varies depending on the type of users in the network and the suitability of the product being marketed. Most of the existing diffusion models do not take this into account. This paper proposes a target adoption model that accounts for both awareness and adoption spread in the network, and a heuristic based discounting approach to find the seed set. The proposed approach is evaluated on different datasets and found to outperform the existing heuristics and discounting approaches. The approach causes maximum adoption in the given social network. © 2017 IEEE.Item Identifying Provenance of Information and Anomalous Paths in Attributed Social Networks(Institute of Electrical and Electronics Engineers Inc., 2018) Trivedi, H.; Bindu, P.V.; Santhi Thilagam, P.S.Information provenance problem is an important and challenging problem in social network analysis and it deals with identifying the origin or source of information spread in a social network. In this paper, an approach for detecting the source of an information spread as well as suspicious anomalous paths in a social network is proposed. An anomalous path is a sequence of nodes that propagates an anomalous information to the given destination nodes who cause an anomalous event. The proposed approach is based on attribute-based anomalies and information cascading technique. The anomalous paths are identified in two steps. The first step assigns an anomalous score to each and every vertex in the given graph based on suspicious attributes. The second step detects the source and suspicious anomalous paths in the network using the anomaly scores. The approach is tested on datasets such as Enron and Facebook to demonstrate its effectiveness. Detecting anomalous paths is useful in several applications including identifying terrorist attacks communication path, disease spreading pattern, and match-fixing hidden path between bookie and a cricketer. © 2018 IEEE.Item Mining social networks for anomalies: Methods and challenges(Academic Press, 2016) Bindu, P.V.; Santhi Thilagam, P.S.Online social networks have received a dramatic increase of interest in the last decade due to the growth of Internet and Web 2.0. They are among the most popular sites on the Internet that are being used in almost all areas of life including education, medical, entertainment, business, and telemarketing. Unfortunately, they have become primary targets for malicious users who attempt to perform illegal activities and cause harm to other users. The unusual behavior of such users can be identified by using anomaly detection techniques. Anomaly detection in social networks refers to the problem of identifying the strange and unexpected behavior of users by exploring the patterns hidden in the networks, as the patterns of interaction of such users deviate significantly from the normal users of the networks. Even though a multitude of anomaly detection methods have been developed for different problem settings, this field is still relatively young and rapidly growing. Hence, there is a growing need for an organized study of the work done in the area of anomaly detection in social networks. In this paper, we provide a comprehensive review of a large set of methods for mining social networks for anomalies by providing a multi-level taxonomy to categorize the existing techniques based on the nature of input network, the type of anomalies they detect, and the underlying anomaly detection approach. In addition, this paper highlights the various application scenarios where these methods have been used, and explores the research challenges and open issues in this field. © 2016 Elsevier Ltd. All rights reserved.Item Discovering suspicious behavior in multilayer social networks(Elsevier Ltd, 2017) Bindu, P.V.; Santhi Thilagam, P.S.; Ahuja, D.Discovering suspicious and illicit behavior in social networks is a significant problem in social network analysis. The patterns of interactions of suspicious users are quite different from their peers and can be identified by using anomaly detection techniques. The existing anomaly detection techniques on social networks focus on networks with only one type of interaction among the users. However, human interactions are inherently multiplex in nature with multiple types of relationships existing among the users, leading to the formation of multilayer social networks. In this paper, we investigate the problem of anomaly detection on multilayer social networks by combining the rich information available in multiple network layers. We propose a pioneer approach namely ADOMS (Anomaly Detection On Multilayer Social networks), an unsupervised, parameter-free, and network feature-based methodology, that automatically detects anomalous users in a multilayer social network and rank them according to their anomalousness. We consider the two well-known anomalous patterns of clique/near-clique and star/near-star anomalies in social networks, and users are ranked according to the degree of similarity of their neighborhoods in different layers to stars or cliques. Experimental results on several real-world multilayer network datasets demonstrate that our approach can effectively detect anomalous nodes in multilayer social networks. © 2017 Elsevier LtdItem Discovering spammer communities in twitter(Springer New York LLC barbara.b.bertram@gsk.com, 2018) Bindu, P.V.; Mishra, R.; Santhi Thilagam, P.S.Online social networks have become immensely popular in recent years and have become the major sources for tracking the reverberation of events and news throughout the world. However, the diversity and popularity of online social networks attract malicious users to inject new forms of spam. Spamming is a malicious activity where a fake user spreads unsolicited messages in the form of bulk message, fraudulent review, malware/virus, hate speech, profanity, or advertising for marketing scam. In addition, it is found that spammers usually form a connected community of spam accounts and use them to spread spam to a large set of legitimate users. Consequently, it is highly desirable to detect such spammer communities existing in social networks. Even though a significant amount of work has been done in the field of detecting spam messages and accounts, not much research has been done in detecting spammer communities and hidden spam accounts. In this work, an unsupervised approach called SpamCom is proposed for detecting spammer communities in Twitter. We model the Twitter network as a multilayer social network and exploit the existence of overlapping community-based features of users represented in the form of Hypergraphs to identify spammers based on their structural behavior and URL characteristics. The use of community-based features, graph and URL characteristics of user accounts, and content similarity among users make our technique very robust and efficient. © 2018, Springer Science+Business Media, LLC, part of Springer Nature.Item Influence maximisation in social networks(Inderscience Publishers, 2019) Tejaswi, V.; Bindu, P.V.; Santhi Thilagam, P.S.Influence maximisation is one of the significant research areas in social network analysis. It helps in identifying influential entities from social networks that can be used in marketing, election campaigns, outbreak detection and so on. Influence maximisation deals with the problem of finding a subset of nodes called seeds in the social network such that these nodes will eventually spread maximum influence in the network. This is an NP-hard problem. The aim of this paper is to provide a complete understanding of the influence maximisation problem. This paper focuses on providing an overview on the influence maximisation problem, and covers three major aspects: 1) different types of inputs required; 2) influence propagation models that map the spread of influence in the network; 3) the approximation algorithms proposed for seed set selection. In addition, we provide the state of the art and describe the open problems in this domain. © 2019 Inderscience Enterprises Ltd.