Complex networks provide a flexible way to represent
heterogeneous connectivity and interactions within real-world
systems. Nowadays, people's lives are immersed in a world full of
diverse and intricate complex networks. These networks not only
provide conveniences that benefit our daily lives, such as enabling
social networking, personalized recommendations, and shopping
promotions. But they also bring certain negative impacts, such as
facilitating the spread of misinformation, rumors, and infectious
diseases. Therefore, developing a comprehensive understanding
of the formation mechanisms, structures, and dynamics of
complex networks in these socio-technical systems remains a
pressing and challenging scientific endeavor. This thesis aims to
explore multiple aspects of the applications of complex network
analysis, with the following main contributions:
First, network dismantling. Network dismantling strategies will be
critical for managing the spread of COVID-19. Public health
interventions like social distancing and creating social bubbles aim
to reduce infections by limiting interactions between social
networks, thus reducing exposure risk. These measures essentially
reconfigure the connections in the underlying contact networks.
From a theoretical perspective, determining the optimal strategy
to fragment networks to disrupt disease transmission maps to the
optimal bond percolation (OBP) problem on networks. OBP
involves selectively removing network connections to fragment the
network into small components to minimize the size of the giant
connected component. This has direct relevance for targeted
social distancing policies that try to maximally disrupt the contact
network with minimal disruption to individuals. In Chapter 4, I will
formally introduce the OBP problem and discuss several heuristic
strategies and benchmark algorithms.
Second, a reputation system based on a network/bipartite graph.
As online platforms like e-commerce, review sites, and social
media grow, effectively evaluating quality and reputation through
rating systems has become critical across many domains.
Typically, an item's reputation is quantified by aggregating ratings
and reviews left by users based on their experiences. However,
user-contributed ratings can be intentionally misleading or biased,
failing to reflect true underlying quality. In particular, certain users
may exhibit consistent biases in their ratings across items, like being
overly critical or lenient. Other users may be motivated to boost or
attack specific targets. Such rating biases can significantly distort
reputation systems and lead to poor recommendations if left
unaccounted for. To address this challenge, evaluating the
reputation of raters themselves becomes vital. We need scalable
computational methods to infer which users provide accurate and
reliable ratings versus those who skew ratings up or down. By
correcting for rating biases, we can better reveal the intrinsic
quality of items. In Chapter 5, we introduce an iterative balancing
(IB) model that alternates between estimating user reputation and
inferring unbiased item quality from the collective ratings.
Experiments on movie rating data demonstrate the IB approach
yields highly consistent results across iterations and effectively filters
out different types of synthetic rating biases.
Third, information popularity prediction on social networks. The
ability to predict the size of information cascades in online social
networks is critical for a variety of applications, including decisionmaking and viral marketing. Traditional methods either rely on
complex time-varying features, which are difficult to extract from
multilingual and cross-platform content, or rely on network
structures and properties, which are often difficult to obtain. To
address these issues, we conducted an empirical study using data
from two well-known social networking platforms (WeChat and
Weibo). The findings suggest that the information cascade process
is best described as an activation-decay dynamic. Based on this,
we develop an Activate-Decay (AD)-based algorithm that can
accurately predict the long-term popularity of online content
based only on the number of early retweets. An indirect
relationship between the peak retweeting amount and the total
propagation amount was also found. Finding the peak of
information diffusion can significantly improve the prediction
accuracy of the model. This content will be introduced in detail in
Chapter 6.
The research presented in this thesis provides valuable insights into
the function and influence of complex networks across various
real-world systems.