Network Structure and Models

Finding the statistical properties of network structure and creating models of networks that can help us to understand the meaning of these properties are the one of the major current challenges in complex network research. The main activity of our research in this area is the analysis and characterization of the network’s structure and the development of models aimed at the understanding of the global behavior of these systems.

Ongoing Projects

Overlapping Community Detection in Dynamic Networks

Community detection is an important topic and has attracted so much interests recently.  In networks, community structure indicates “groups of vertices such that vertices within a group are much more connected to each other than to the rest of the network”. Individuals can belong to multiple groups so communities can have overlaps named overlapping communities. Community detection is so important because communities show patterns of people behavior and considering overlapping communities can help us to have more accurate analysis and prediction of behaviors.

Traditional researches, study the communities in static networks but in real, communities evolve in time and the dynamic nature of network should be considered. In this research, we want to study dynamic networks in discrete time steps (snapshots) and detect and track communities in them.

People involved: Mahsa Ghorbani, Ali Khodadadi, Hamid R. Rabiee

___________________________________

Community Detection in social networks using Node Attributes and Network Topology

Social networks has become an interest research field in recent years. One open problem is to detect communities in social networks. If we represent a network as a graph, a community is set of nodes that are densely interconnected and have similar attributes and behaviors. These nodes interact with each other more frequently than with those outside the group. Many existing community detection algorithms mainly focus on topological structure of the network, while in many real-world networks we have another source of information; node attributes. In this research, we concentrated on community detection using network structure and node attributes.

People involved: Mohammad R. Radmanesh, Ali Khodadadi, Hamid R. Rabiee

___________________________________

Community Detection using Map-Reduce

One of the main challenges in community detection is the scalability of the methods. Many real social networks have millions of nodes and edges. This huge size makes  many community detection methods to not work properly over these real big networks. One way to deal with this challenge is to use cluster computing. Map-Reduce paradigm is one of the most famous cluster computing models that has gained many attention in recent years. In this research we will compare practically some cluster computing models for network data and will compare their efficiency over community detection problem.

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

___________________________________

Using Compressive Sensing (CS) to Efficiently Measure and Analyze the Functionality of Brain Network

In recent years, many studies have been conducted on modeling the structure and behavior of the human brain network using the complex networks. Some of these researches have shown that several changes in this network happened caused by diseases such as Alzheimer’s, epilepsy and schizophrenia. Accordingly, the neuroimaging methods as unique tools for early diagnosis of these disorders have been studying.Among these methods, electroencephalogram signal (EEG) is an accessible and affordable approach with sufficient temporal resolution, which has been used for the possible examinations.
In this project, we propose a novel and general framework in the context of Compressive Sensing (CS) to efficiently measure and analyze the functionality of brain network. In this framework, we will use the concepts of graph theory and also EEG data to achieve an accurate model. Previous works have focused on the undirected brain network, although in this project, the directed networks are considered and appropriate framework to extract meaningful functional brain networks will be proposed. Then, by extracting the directed brain network, various network measures (e.g., shortest path length, global efficiency, local efficiency, clustering, and correlation) will be investigated. Furthermore, we try to properly detect the most important regions (nodes) that establish more connections to the other regions. Finally, the network controllability and observability will be analyzed.

People involved: Saeedeh Afshari, Hamid R. Rabiee

Past Projects

 

Community Detection in Complex Networks

In recent years, a considerable amount of research has been devoted to identifying community structure, or clustering, in networks. A community is a set of nodes that has more connections between its members than to the rest of the network. Such clusters, can be considered as independent part of a network, playing a similar role like. Community detection is very important in sociology, biology. Despite in spite of the many methods which have been proposed over the past few years, this problem is so hard and still open. The main difficulty is that it is not a well-defined problem, where there is still confusion about the definition of community or the evaluation of partitions. In addition, nodes can belong to different communities and that groups may in turn represent subunits of larger modules. In this project we investigate various topics about the community detection problem such as the definition of the basic elements, main developed methods, the significance of clustering, the evaluation of methods and the applications to real-world complex networks. There are three categories of community detection algorithms. first category is called classical algorithms.in this categories, base of clustering of graph is similarity between nodes.this categories is defined in euclidean space and appropriate for data clustering. second category, divisive algorithms, is based on removing edge that locate between clusters. some of algorithms in these category are GN(Grivan & Newman) and Radicchi. third category,modularity based algorithms, is based on optimizing the modularity function with approximate algorithm. best algorithm in this category is extremal.

People involved: Arezoo Rajabi, Maryam Tahani, Mostafa Salehi, Hamid R. Rabiee

___________________________________

Network Topology Inference from Incomplete Data

Data collection is one of the first steps in the analysis of complex networks, and during the last decade, a large number of studies have been conducted on it. However, due to the large scale of these networks, almost never is there any complete information about their different aspects. Therefore, the analysis of a network is usually done based on incomplete data which can cause a significant alternation in our inferences and estimates about the networks’ properties. Consequently, the possibility of predicting the hidden part of the network and the way to do it, that is the network completion problem, is of significant importance. However, some of the properties in large networks, such as the sparsity in their structure, provide the foundation to link this problem to sparse signal recovery methods like compressive sensing or low-rank matrix completion. The aim of this project is to determine, analyze, and provide an efficient solution to the challenges of inferring the network structure from incomplete data.

People involved: Payam Siyari, Hamid R. Mahyar, Mostafa Salehi, Hamid R. Rabiee

___________________________________

Network Compressive Sensing in Complex Networks with Topological Constraints

Compressive sensing is a new paradigm in signal processing theory, which proposes to sample and recover sparse signals efficiently. According to CS theory, any sufficiently compressible signal can be accurately recovered from a small number of non-adaptive, randomized linear projection samples. Compressed sensing has drawn much attention in the signal processing and general systems community in the last couple of years, but its role in networking is still in its early stages. One key question in CS is to design a small number of non-adaptive measurements such that all the data up to certain Sparsity can be correctly recovered. Most existing literature, rely critically on the assumption that any subset of the values can be aggregated together, which is not realistic in network problems with topological constraints where only nodes that form a path or a cycle on the underlying graph, or induce a connected sub graph can be aggregated together in the same measurement. In this project, we want to provide explicit measurement constructions for applying CS in networks subject to topological constraints. Moreover, it is desired that our proposed solution be applicable in networks with limited information about their connectivity.

People involved: Zakieh Hashemifar, Hamid R. Mahyar, Hamid R. Rabiee

A Complex Network Model for Video Streaming in P2P Networks

Complex networks describe a wide range of networked systems in technology, nature and society, such as Internet, WWW networks, P2P networks, biological networks and social interactions. P2P networks have recently attracted many users and also researchers on the Internet. One of the most successful Applications of P2P networks is streaming the video. In this research we focus on mesh-pull based streaming networks and our goal is to propose a complex network model for such a P2PIPTV topology. To reach to this aim we consider the microscopic processes on each node that affects the assembling and evolving the network and propose a growth model which matches to mesh-based P2P protocols. The topological characteristics for this model will be investigated both analytically and by simulation. The analytical results will be obtained by using the continuum theory, the master equation approach and the rate equation approach which have been used to model scale free evolving networks previously. The model will be verified by real measurements and simulations. The results could be used to optimize such networks and to develop more realistic simulation for P2P mesh-based networks.

People involved: Amir Farzad, Hamid R. Rabiee

___________________________________

Modeling Brain Functional Networks using High Density Electroencephalography Data

In this project we address the problem of modeling brain functional networks using Electroencephalography (EEG) data. We process the high density EEGs of some healthy subjects and extract the topology of their brain network is extracted by employing partial correlation analysis. We study the statistical and dynamical properties of the brain functional networks by monitoring some measurement in the network. Comparing these parameters between different groups, e.g. healthy subjects and patients suffering from a brain disorder, may shed light on how the disorder affects on the functional connectivity of the brain regions.

People involved: Mostafa Salehi, Mahdi Jalili, Hamid R. Rabiee

___________________________________

Motif Structure and Cooperation in Real-World Complex Networks

 

Networks of dynamical nodes serve as generic models for real-world systems in many branches of science ranging from mathematics to physics, technology, sociology and biology. Collective behavior of agents interacting over complex networks is important in many applications. The cooperation between selfish individuals is one of the most interesting collective phenomena. In this paper we address the interplay between the motifs’ cooperation properties and their abundance in a number of real-world networks including yeast protein–protein interaction, human brain, protein structure, email communication, dolphins’ social interaction, Zachary karate club and Net-science co-authorship networks. First, the amount of cooperativity for all possible undirected subgraphs with three to six nodes is calculated. To this end, the evolutionary dynamics of the Prisoner’s Dilemma game is considered and the cooperativity of each subgraph is calculated as the percentage of cooperating agents at the end of the simulation time. Then, the three- to six-node motifs are extracted for each network. The significance of the abundance of a motif, represented by a Z-value, is obtained by comparing them with some properly randomized versions of the original network. We found that there is always a group of motifs showing a significant inverse correlation between their cooperativity amount and Z-value, i.e. the more the Z-value the less the amount of cooperativity. This suggests that networks composed of well-structured units do not have good cooperativity properties.

People involved: Mostafa Salehi, Hamid R. Rabiee, Mahdi Jalili

___________________________________

Navigation and Searching Strategies in Dynamical Complex Networks

Milgram’s pioneering experiment and related works about the small-world property, elucidate two interesting aspects of social networks: (1) relatively short paths exist in large size networks; (2) individuals are able to find short paths even in the absence of a global knowledge of the network. While the former feature is recovered in the various models , the latter property is not yet clearly understood. The ability to navigate and search for shortest paths in a network without knowledge on its whole topological structure(decentralized search)is a relevant issue, not only in social systems, but also in optimization of information finding from the World Wide Web, traffic way-finding in a city, transport of information packets on the Internet, or diffusion of signaling molecules in a biological cell. If it were possible to construct artificial networks that were easy to navigate in the same way that social networks appear to be, it has been suggested they could be used to build efficient database structures or better peer-to-peer computer networks. In this project, we review some of the studies on the subject. Two main approaches have been followed: one is based on finding the best strategy for constructing a path to a target node from an initial node by using local or geometric information; the second aims at assessing the most efficient network structure for path searching, once the way of finding a path is fixed. In addition, we will investigate if the topological information of the underlying networks can be drawn by comparing the results of the different search strategies.

People involved: Akram Daruki, Mostafa Salehi, Hamid R. Rabiee, Ebadollah Mahmoodian

___________________________________

Resiliency of Complex Networks to Targeted Attacks

Networks are everywhere. Social networks, airway networks, computer networks and many others. These networks play a significant role in the life of human beings and this obligates their study. One of the most important issues in networks, is their robustness, security and dependability. The failure of these networks may have two kind of reasons, whether because of failure of some random nodes or by means of a targeted attack played by an adversary. It has been observed that complex networks have scale-free structure and are robust to random attacks but rather fragile in case of a targeted attacks. In this project we inspect the vulnerability of these networks against targeted attacks, the effects of these attacks, the measures of these networks and finding central nodes with the most effects on the networks behaviour.

This project was done in two separate phases: Phase I) This phase began with a survey of different measures for centrality and different algorithms for attacking complex networks. Then I implemented a framework for generating, attacking and analyzing the properties of different models of complex networks, i.e. random graphs, small-world networks and scale-free networks. In each layer of this three layer framework, the outputs are saved in the file system and are loaded to memory in the next layer. Phase II) In the second phase, I designed a crawling machine for twitter. This crawler is implemented in java and uses the twitter api for connecting to the twitter web server. I used MySQL DBMS for managing the data and the network of twitter users was captured and saved using it. Then I imported these data into Matlab and used different algorithms for attacking this so called twitter network. The results were analyzed and illustrated and it was shown that this network acts the same as the models investigated in phase I.

People involved: Shayan Pooya, Mostafa Salehi, 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