Network Data Mining and Analysis

The following sections are included:

• East China Normal University Scientific Reports
• Preface
• About the Authors
• Acknowledgments
• Contents

In recent years, with the development of Internet technology, online social networks have gradually changed people’s lives. Facebook, Twitter, Sina Weibo, etc., have become more and more popular. So far, there are more than 2.2 billion and 500 million registered users on Facebook and Twitter, respectively. Every day, hundreds of millions of people spend a lot of time on the social network platforms to share, communicate, connect, interact, and create massive information, which has directly contributed to the arrival of the era of big data. Large amounts of data is generated in the online social networks, including users’ sharing, relationships, and interactions, etc. These data provides an opportunity for us to learn about the patterns of interaction between users, to detect network events, and to predict user behaviors. Thus, massive social network data has great research value and huge market applications. Social network mining, which is a new research field with rapid growth, has become a hot research topic. In this research area, social connections are important and inseparable features of social networks. Compared with traditional data mining, we need some new methodologies to analyze and mine the social network data which are related to the social psychology, statistics, spectral analysis, probabilistic theory, graph theory, and graph mining, and so on.

We live in a connected world. The transportation network has made travel much more convenient; the financial network has made people’s consumption and financial management very easy; and communication networks have helped spread information very quickly. Network brings people’s lives closer and promotes the development of industries rapidly. These connected networks can be represented by the different graphs. The information form networks can help us to predict connections, make user portraits, recommend production, etc. In this chapter, we will introduce some basic concepts about graphs in network mining.

In this chapter, we define the $\mathcal{\text{R}}$-energy (Gao et al., 2013) as a new measure of network robustness based on the spectral analysis of the normalized Laplacian matrix. Compared to the existing robustness metrics, such as the set of connectivity measurements and the set of expansion measurements, our proposed $\mathcal{\text{R}}$-energy mainly has two advantages. First, $\mathcal{\text{R}}$-energy can evaluate the robustness of disconnected networks. However, all existing robustness measurements cannot be applied for evaluating the robustness of disconnected networks. Second, it is efficient to be computed with a time complexity of O(|V | + |E|), where V and E are the vertex set and edge set of the network, respectively. As shown in the empirical study, our proposed algorithm takes as little as 40 seconds to compute $\mathcal{\text{R}}$-energy for a network with about 5M vertices and 69M edges. We also apply our proposed $\mathcal{\text{R}}$-energy to detect events occurring in a dynamic Twitter network with about 130K users and discover interesting weekly tweeting trends.

In this chapter, we propose an unsupervised method, collective network linkage (CNL) (Gao et al., 2015), to link users across heterogeneous social networks. CNL incorporates heterogeneous attributes and social features unique to social network users, handles missing data, and performs in a collective manner. CNL is highly accurate and efficient even without training data. We evaluate CNL on reidentifying users for the same social network, as well as linking users across different social networks. Our experimental results on a Twitter network and another Foursquare network demonstrate that CNL performs very well for the above two tasks, and its accuracy is superior than the supervised Mobius approach.

In this chapter, we aim to detect a dense sub-structure from bipartite graphs, called quasi-biclique community (QBC). Compared to the definition of biclique, a QBC allows a small number of inter-set edges to be missing. We propose an algorithm, which consists of pruning stage and verification stage, to detect all maximal QBCs (MQBCs) from bipartite graphs. In the pruning stage, we drive three pruning rules to reduce the sizes of candidate graphs and the number of candidate graphs. In the verification stage, we employ an enumeration tree to enumerate and verify all subgraphs of a candidate graph in a top-down fashion. We have conducted extensive experiments using two real networks to demonstrate the efficiency and accuracy of the proposed algorithm.

In this chapter, we define a dense sub-structure in a signed graph, called quasi-antagonistic communities (QACs) (Gao et al., 2016). Instead of requiring complete set of negative links across its groups, a QAC allows a small number of inter-group negative links to be missing. We propose an algorithm, MASCOT, to find all maximal quasiantagonistic communities (MQACs). MASCOT consists of two stages: pruning and enumeration. Based on the properties of QAC, we propose four pruning rules to reduce the size of candidate graphs in the pruning stage. We use an enumeration tree to enumerate all strongly connected subgraphs in a top-down fashion in the second stage before they are used to construct MQACs. We have conducted extensive experiments using synthetic signed graphs and two real networks to demonstrate the efficiency and accuracy of the MASCOT algorithm. We have also found that detecting MQACs helps us to predict the signs of links.

The following sections are included:

• Conclusions
• Discussion of Future Directions

The following sections are included:

• Bibliography
• Index