Information Networks

The complex networks (such as social systems) of interactions among a group of individuals plays a fundamental role in the spread of information and influence. Such effects have been observed in many cases, when an behavior gains sudden widespread popularity. We would like to understand how the structure of the network affects the spread of information, influence and viruses over the network. We monitor the spread of information on the complex networks. We ask what are the typical structural patterns of information propagation? We aim in creating models that help us predict future and identify influential nodes.

Ongoing Projects

Community Detection in Social Networks by using Information from Diffusion Network

Nowadays, social networks play a fundamental role in the spread of information by the quality and rapid reception of information. One of the main characteristics of these networks is their modular structure. Each module in a network is called a community. Qualitatively, a community is a set of nodes which connect each other densely and connect to the rest of network’s nodes sparsely.
A lot of research has been done to propose community detection algorithms and most of them presume access to topological information of graphs. Due to the growth of social networks and high overhead caused by various users and their communications, gathering full information of nodes’ connections may not be feasible therefore applying a traditional community detection algorithm seems to be impossible.
On important process taking place on social networks is diffusion. Diffusion behavior on a network is closely related to its community structure. Because of the dense relations between nodes in a community, whenever information reaches one node it spreads through the community instantly. On the other hand, boundary nodes (nodes which have links to other communities) have an important role in information propagation from one community to others.
The aim of this project is to define the community structure of social networks by utilizing information from nodes diffusion behavior.

People involved: Maryam Ramezani, Maryam Tahani, Arezoo Rajabi, Ali Khodadadi, Hamid R. Rabiee

___________________________________

Sparse Recovery in Peer-to-Peer Networks via Compressive Sensing

Compressive Sensing (CS) is one of the most interesting new research areas on both signal processing and information theory. Its purpose is to recover the desired sparse signal (data), from a small number of non-adaptivelinear measurements. The applications of CS in networking are still in its early stages and a few recent works have been proposed to retrieve the data stored on the components (nodes/links) of a network using CS theory. In almost all of these works, a single centralized node is responsible for sampling, processing and recovering the desired information from the entire network.
In this M.Sc. thesis, we are going to devolve those responsibilities to all nodes in order to have a decentralized management, similar to P2P systems. In other words, all nodes collaborate with each other in order to accurately recover the hidden data of the network and finally each node recovers the desired data independently.

People involved: Ali Fattaholmanan, Ali Khodadadi, Hamid R. Rabiee

___________________________________

Link Prediction in Social Networks Using the Diffusion Network Characteristics

Nowadays Social networks play a leading role in connecting people with similar interests in order to communicate and also exchange data and information. This spread of information through social links of the underlying network can itself build an overlaying diffusion network. Predicting future links based on the network’s current state is considered as link prediction. There are two main approaches in this field, topological or feature based. In the prior one, topological information of underlying social network and in the latter, feature similarities between nodes can help us predict future links. Although link prediction in social networks has been widely studied, using diffusion network information to predict links can still be an open area of interest especially when our knowledge of network is incomplete. This issue arises particularly in networks with millions of users whose relations and attributes can never be captured thoroughly. In such networks time consumption can be a drawback of current algorithms. So introducing fast and accurate link prediction methods using the overlaying diffusion network’s information can be of significant importance. In this project, we aim to introduce a fast and accurate algorithm for link prediction in social networks using the overlaying diffusion network characteristics.

People involved: Tahora H. Nazer, Maryam Tahani, Hamid R. Rabiee

Past Projects

___________________________________

Identifying the Influential Propagating Nodes in Complex Networks

The social network of interactions within a group of individuals plays fundamental role in the spread of information, ideas, and innovations. In fact, a piece of information, such as the URL of a website that provides a new valuable service, can spread from one individual to another through the social network in the form of “word-of-mouth” communication. Thus, when we plan to market a new product, promote an innovation, or spread a new topic among a group of individuals, we can exploit social network effects. Indeed, we can target a small number of influential individuals (e.g., giving free samples of the product, demonstrating the innovation, or offering the topic), and trigger a cascade of influence by which friends will recommend the product, promote the innovation, or propagate the topic to other friends. Therefore, given a social network represented by a directed graph, a positive integer k, and a probabilistic model for the process by which a certain information spreads through the network, it is an important research issue in terms of sociology and viral marketing to find such a target set A of k nodes that maximizes the expected number of adopters of the information if A initially adopts it.

People involved: Baharan Mirzasoleiman, Hamid R. Maghbooli, Mostafa Salehi, Hamid R. Rabiee

___________________________________

Cost Effective Immunization of Social Network

There is much interest in the question of how to immunize a population, or a computer network such as the Internet, with a minimal number of immunization doses. This question is very important since in many cases the number of immunization doses is limited or very expensive. This question is mathematically equivalent to asking how to fragment a given network with a minimum number of node removals. To achieve this goal, many immunization strategies have been developed recently, ranging from local strategies, like acquaintance immunization to global strategies like targeted immunization. The effect of immunization strategies are often studied by ignoring the vaccination costs or assuming an infinite budget; however, this might not be the case in real situations. In this work, we aim at a more natural objective by finding an effective immunization strategy considering a limited budget. Indeed, many people might be eager to pay a price to become immunized against an epidemic disease. This is a valid scenario in the case of computer viruses. An efficient immunization strategy can make use of these values to immunize a larger fraction of the individuals in a network. In particular, we are interested in reducing the minimum budget required for globally immunization the network against infectious using the suitable immunization approaches.

People involved: Mahmoodreza Babaee, Mostafa Salehi, Hamid R. Rabiee

___________________________________

Extracting Cascaded Information Networks From Social Networks

Cascading behavior, diffusion and spreading of ideas, innovation, information, influence, viruses and diseases are fundamental processes taking place in networks.While it is often possible to directly observe when nodes become infected, observing individual transmissions (i.e., who infects whom or who influences whom) is typically very difficult. Furthermore, in many applications, the underlying network over which the diffusions and propagations spread is actually unobserved.In this project, Given the times when nodes adopt pieces of information or become infected, we identify the optimal network that best explains the observed infection times. Since the optimization problem is NP-hard to solve exactly, we develop an efficient approximation algorithm that scales to large datasets and in practice gives provably near-optimal performance.We will use from recent approaches such as NetInf for comparison and improve the performance.

People involved: Motahareh Eslami, Mostafa Salehi, Hamid R. Rabiee

___________________________________

Maximizing the Spread of Social Influence in Social Networks

Social networks are social structures made of nodes that are tied by one or more social relations. They are complex networks mainly represented with the mean of graph structure and are assumed to reflect the real social phenomena. That’s the reason so many sociological characteristics of humans as individual or them within a group are studied in this field. One of these studied characteristics is social influence which focused on diffusion of information or innovations. Several fields are involved in this research area, like modeling the diffusion, maximizing spread of it or finding charismas or central people. We aim to exploit this social influence in to help understand how patterns of human contact aid or inhibit the spread of a specific phenomenon.

People involved: Mina Doroud, Hamid R. Rabiee

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Complex Networks | Digital Media Lab