In this paper, we address the challenge of discovering hidden nodes in unknown social networks, formulating three types of hidden-node discovery problems, namely, Sybil-node discovery, peripheral-node discovery, and influencer discovery. We tackle these problems by employing a graph exploration framework grounded in machine learning. Leveraging the structure of the subgraph gradually obtained from graph exploration, we construct prediction models to identify target hidden nodes in unknown social graphs. Through empirical investigations of real social graphs, we investigate the efficiency of graph exploration strategies in uncovering hidden nodes. Our results show that our graph exploration strategies discover hidden nodes with an efficiency comparable to that when the graph structure is known. Specifically, the query cost of discovering 10% of the hidden nodes is at most only 1.2 times that when the topology is known, and the query-cost multiplier for discovering 90% of the hidden nodes is at most only 1.4. Furthermore, our results suggest that using node embeddings, which are low-dimensional vector representations of nodes, for hidden-node discovery is a double-edged sword: it is effective in certain scenarios but sometimes degrades the efficiency of node discovery. Guided by this observation, we examine the effectiveness of using a bandit algorithm to combine the prediction models that use node embeddings with those that do not, and our analysis shows that the bandit-based graph exploration strategy achieves efficient node discovery across a wide array of settings.

Generating graphs using computational models is a critical activity with numerous applications, including social network research and biological network modeling. Despite sig-nificant breakthroughs in graph-generating technologies, modern machine learning for simulating complex real-world networks still requires effective improvement. Specifically, the ability to conditionally generate graphs while accounting for local and global structural elements has not been fully explored. This study presents a novel approach to graph generation that combines Transformer encoders' strong contextual understanding with Long Short Term Memory (LSTM) decoders' sequence modeling capabilities, all within a Conditional Variational Auto Encoder (CVAE) framework. Our methodology aims to fine-tune the structural features of generated graphs more accurately, representing an advancement in conditional graph generation. Our results, based on extensive tests versus standard generative models utilizing graph datasets, show that our model can more clearly tune global-level structural features' values better than conventional models.

In recent years, there has been a growing demand for techniques to artificially generate graphs. Various proposals have been made for graph generation models using machine learning. Among these models, GraphTune is a model that allows to specify the features of the generated graphs. GraphTune has not achieved sufficient accuracy when specified values are in ranges where there are few samples in the training dataset. Therefore, in this paper, we propose a method to improve the accuracy of GraphTune by retraining it using graphs generated by the model itself. Through experiments using real-world graphs, we demonstrate that the higher accuracy can be achieved compared to the conventional method.

We investigate the structural characteristics of ego networks of influential Twitter users. While existing studies have elucidated the global characteristics of influencers in a social network, it remains unclear what differences exist in the local structure of social networks between influencers and non-influencers. Using four Twitter datasets, we calculate two types of influence scores for each user, called direct influence and indirect influence. Then, we compare several measures of ego networks between users with high influence scores (influencers) and everyone else (non-influencers). Our results show that influencers with strong direct influence have relatively lower values for their average degree, clustering coefficient, and reciprocity, and higher centralization than non-influencers, which suggests that influencers have different ego-network structures than non-influencers. In contrast, our results also show that ego-network structures of users with strong indirect influence are not very different from those of other users, which suggests that the ego-network structure of a user is not useful for estimating their indirect influence.

In the field of communication network management, graph-based simulations using network topology models represented as graphs are widely adopted. In graph-based simulations, because there is a limited number of real network graph data that researchers and experts can access, the technique of generating graphs that mimic the features of real networks using graph generative models is essential. In this context, machine learning-based graph generative models have been rapidly advancing recently. In particular, in terms of the accuracy of reproducing the features of generated graphs, sequence data-based graph generative models have been successful. In this paper, we propose a method based on 2nd-order random walk as an alternative to DFS code, which is used for graph-to-sequence conversion in GraphTune, one of the sequence data-based graph generative models. We conducted experiments on a small dataset with limited diversity on a real graph dataset and confirmed that the model using the proposed method is at best 54.68% more accurate than the model using the conventional method.

Predicting which users are likely to leave a given online community has been studied for several types of platforms. The problem of predicting whether a given user is going to leave a given community is referred to as the user churn prediction problem. Existing studies have typically used features obtained from the user’s activity records in the community. In contrast, we use both social-network and inter-community features, as well as the basic features used in existing studies. In this paper, we focus on Reddit as an example of a popular online community platform. We extract several features from records of comments in Reddit communities, then use them to construct models for user churn prediction and to evaluate their prediction accuracy. Our results show that among the several features used in this paper, the number of comments posted by users is most effective at predicting user churn, and the model using only the number of posted comments achieved an F-1 score of 0.78. Although social-network and inter-community features can be used for user churn prediction, combining them with basic activity features does not improve prediction accuracy.

A graph is a very common and powerful data structure used for modeling communication and social networks. Models that generate graphs with arbitrary features are important basic technologies in repeated simulations of networks and prediction of topology changes. Although existing generative models for graphs are useful for providing graphs similar to real-world graphs, graph generation models with tunable features have been less explored in the field. Previously, we have proposed GraphTune, a generative model for graphs that continuously tune specific graph features of generated graphs while maintaining most of the features of a given graph dataset. However, the tuning accuracy of graph features in GraphTune has not been sufficient for practical applications. In this paper, we propose a method to improve the accuracy of GraphTune by adding a new mechanism to feed back errors of graph features of generated graphs and by training them alternately and independently. Experiments on a real-world graph dataset showed that the features in the generated graphs are accurately tuned compared with conventional models.

Identifying influencers in a given social network has become an important research problem for various applications, including accelerating the spread of information in viral marketing and preventing the spread of fake news and rumors. The literature contains a rich body of studies on identifying influential source spreaders who can spread their own messages to many other nodes. In contrast, the identification of influential brokers who can spread other nodes' messages to many nodes has not been fully explored. Theoretical and empirical studies suggest that involvement of both influential source spreaders and brokers is a key to facilitating large-scale information diffusion cascades. Therefore, this paper explores ways to identify influential brokers from a given social network. By using three social media datasets, we investigate the characteristics of influential brokers by comparing them with influential source spreaders and central nodes obtained from centrality measures. Our results show that (i) most of the influential source spreaders are not influential brokers (and vice versa) and (ii) the overlap between central nodes and influential brokers is small (less than 15%) in Twitter datasets. We also tackle the problem of identifying influential brokers from centrality measures and node embeddings, and we examine the effectiveness of social network features in the broker identification task. Our results show that (iii) although a single centrality measure cannot characterize influential brokers well, prediction models using node embedding features achieve F1 scores of 0.35--0.68, suggesting the effectiveness of social network features for identifying influential brokers.

Although beneficial information abounds on social media, the dissemination of harmful information such as so-called "fake news" has become a serious issue. Therefore, many researchers have devoted considerable effort to limiting the diffusion of harmful information. A promising approach to limiting diffusion of such information is link deletion methods in social networks. Link deletion methods have been shown to be effective in reducing the size of information diffusion cascades generated by synthetic models on a given social network. In this study, we evaluate the effectiveness of link deletion methods on Twitter by using actual logs of retweet cascades, rather than by using synthetic diffusion models. Our results show that even after deleting 50% of links detected by the NetMelt method from a Twitter social network, the size of tweet cascades after link deletion is estimated to be only 50% the original size, which suggests that the effectiveness of the link deletion strategy for suppressing information diffusion on Twitter is limited. Moreover, our results also show that there is a considerable number of cascades with many seed users, which renders link deletion methods inefficient.

As a long-standing topic of considerable research interest, influence maximization involves finding a few influential nodes in a social network. Building on the rich existing body of literature on influence maximization, a recent emerging trend is the use of real data from information diffusion cascades. However, although data-based influence maximization is expected to be a promising approach, its evaluation remains limited. In this paper, by using a Twitter dataset of retweets among ~0.3 million users for two years, the effectiveness of the data-based influence maximization algorithm DiffuGreedy is evaluated comprehensively. The key findings are as follows. 1) Compared with using an existing model-based influence maximization algorithm on the Twitter dataset, DiffuGreedy scores 20–30% higher in distinct nodes influenced, which is an index for evaluating the effectiveness of influence maximization algorithms. 2) When using a training period that is either too long (i.e., one year or longer) or too short (i.e., one day or shorter), DiffuGreedy is less effective than the existing model-based influence maximization algorithm. 3) There are some short-term influencers who are not influential in the training period but who eventually attract attention from other users in the test period, and finding these short-term influencers is key to improving the effectiveness of DiffuGreedy. However, the present results suggest that finding short-term influencers is a difficult task.

With the development of graph applications, generative models for graphs have been more crucial. Classically, stochastic models that generate graphs with a pre-defined probability of edges and nodes have been studied. Recently, some models that reproduce the structural features of graphs by learning from actual graph data using machine learning have been studied. However, in these conventional studies based on machine learning, structural features of graphs can be learned from data, but it is not possible to tune features and generate graphs with specific features. In this paper, we propose a generative model that can tune specific features, while learning structural features of a graph from data. With a dataset of graphs with various features generated by a stochastic model, we confirm that our model can generate a graph with specific features.

Influence maximization in a social network has been intensively studied, motivated by its application to so-called viral marketing. The influence maximization problem is formulated as a combinatorial optimization problem on a graph that aims to identify a small set of influential nodes (i.e., seed nodes) such that the expected size of the influence cascade triggered by the seed nodes is maximized. In general, it is difficult in practice to obtain the complete knowledge on large-scale networks. Therefore, a problem of identifying a set of influential seed nodes only from a partial structure of the network obtained from network sampling strategies has also been studied in recent years. To achieve efficient influence propagation in unknown networks, the number of sample nodes must be determined appropriately for obtaining a partial structure of the network. In this paper, we clarify the relation between the sample size and the expected size of influence cascade triggered by the seed nodes through mathematical analyses. Specifically, we derive the expected size of influence cascade with random node sampling and degree-based seed node selection. Through several numerical examples using datasets of real social networks, we also investigate the implication of our analysis results to influence maximization on unknown social networks.

While online communities are important platforms for various social activities, many online communities fail to survive, which motivates researchers to investigate factors affecting the growth and survival of online communities. We comprehensively examine the effects of a wide variety of social network features on the growth and survival of communities in Reddit. We show that several social network features, including clique ratio, density, clustering coefficient, reciprocity and centralization, have significant effects on the survival of communities. In contrast, we also show that social network features examined in this paper only have weak effects on the growth of communities. Moreover, we conducted experiments predicting future growth and survival of online communities from social network features. The results show that social network features are useful for predicting the survival of communities but not for predicting their growth.

Both practitioners and researchers are becoming increasingly interested in viral marketing. For viral marketing on social media, it is important to find influencers who can spread information to many other users. Although finding influencers on social media is a topic of much research interest in the field of network science, most previous studies ignored the time evolution of the influence of social media users. In this paper, we investigate the time evolution of the influence of Twitter users. We construct a social network of 0.3 million Twitter users, extract the central nodes in the network using five centrality measures, and investigate how the actual influence of those central nodes changes over a year. We show that the overlap between the central nodes and actual influencers did not change drastically during the one-year period, suggesting that the influence of central nodes is stable over time.

Influence maximization is a combinatorial optimization problem on a graph: Given a social network, an influence maximization algorithm aims to find a set of influential (seed) nodes in the network such that the expected number of nodes influenced by the seed nodes is maximized under the given cascade model. Most influence maximization algorithms proposed in the literature assume that ground-truth influence spread probabilities are available. In reality, however, it is natural to assume that there exists a deviation of the influence spread probability used in the influence maximization algorithms from actual influence spread probability. In this paper, we examine the robustness of existing influence maximization algorithms against non-adversarial perturbations in influence spread probabilities. Our results show that the effectiveness of state-of-the-art approximation and heuristic algorithms may be significantly degraded, and lightweight heuristic algorithms can outperform state-of-the-art algorithms when the perturbations are large.

Recent research trends in network science are shifting from the analysis of single-layer networks to the analysis of multilayer networks. In particular, the robustness of multilayer networks has been actively studied. There exist two popular multilayer network models: one is interdependent network, and the other is multiplex network. We aim to construct a methodology for effectively improving the robustness of multiplex networks against layer node-based attack. As the first step to achieve this goal, in this paper, we examine the effectiveness of existing link addition strategies, which are proposed for interdependent networks, for improving the robustness of multiplex networks. Through the network attack simulations, we show that the strategic link addition can effectively improve the robustness of multiplex networks. Moreover, link addition strategies are suggested to be effective particularly when a large number of nodes are attacked.

Several indices for estimating the influence of social media users have been proposed. Most such indices are obtained from the topological structure of a social network that represents relations among social media users. However, several errors are typically contained in such social network structures because of missing data, false data, or poor node/link sampling from the social network. In this paper, we investigate the effects of node sampling from a social network on the effectiveness of indices for estimating the influence of social media users. We compare the estimated influence of users, as obtained from a sampled social network, with their actual influence. Our experimental results show that using biased sampling methods, such as sample edge count, is a more effective approach than random sampling for estimating user influence, and that the use of random sampling to obtain the structure of a social network significantly affects the effectiveness of indices for estimating user influence, which may make indices useless.

We propose a novel problem called influence maximization for unknown graphs, and propose a heuristic algorithm for the problem. Influence maximization is the problem of detecting a set of influential nodes in a social network, which represents social relationships among individuals. Influence maximization has been actively studied, and several algorithms have been proposed in the literature. The existing algorithms use the entire topological structure of a social network. In practice, however, complete knowledge of the topological structure of a social network is typically difficult to obtain. We therefore tackle an influence maximization problem for unknown graphs. As a solution for this problem, we propose a heuristic algorithm, which we call IMUG (Influence Maximization for Unknown Graphs). Through extensive simulations, we show that the proposed algorithm achieves 60--90% of the influence spread of the algorithms using the entire social network topology, even when only 1--10% of the social network topology is known. These results indicate that we can achieve a reasonable influence spread even when knowledge of the social network topology is severely limited.

In this paper, we extensively evaluate the effectiveness of using a user's social media activities for estimating degree of depression. As ground truth data, we use the results of a web-based questionnaire for measuring degree of depression of Twitter users. We extract several features from the activity histories of Twitter users. By leveraging these features, we construct models for estimating the presence of active depression. Through experiments, we show that (1) features obtained from user activities can be used to predict depression of users with an accuracy of 69%, (2) topics of tweets estimated with a topic model are useful features, (3) approximately two months of observation data are necessary for recognizing depression, and longer observation periods do not contribute to improving the accuracy of estimation for current depression; sometimes, longer periods worsen the accuracy.

Research on social network analysis (SNA) has been actively pursued. Most SNAs focus on either social relationship networks (e.g., Friendship and trust networks) or social interaction networks (e.g., Email and phone call networks). It is expected that the social relationship network and social interaction network of a group would be closely related to each other. For instance, people in the same community in a social relationship network are expected to communicate with each other more frequently than with people in different communities. To the best of our knowledge, however, there is not yet any empirical evidence to support the existence of such interaction locality in large-scale online social networks. This paper aims to bridge the evidence gap between intuition about interaction locality and confirmation that it occurs. We investigate the strength of interaction locality in large-scale social networks by analyzing several types of data: logs of mobile phone calls, email messages, and message exchanges in a social networking service. Our results show that strong interaction locality is observed equally in the three datasets and suggest that the strength of the interaction locality is fractal, by which we mean that the strength is invariant with regard to the scale of the community.

Social network analysis has been actively pursued to provide an understanding of complex social phenomena. However, graphs used for social network analyses generally contain several errors in their nodes, links, and link weights. In recent years, huge amount of data representing human-to-human interactions are available, and their availability enables us to obtain various types of real social networks. In this paper, we investigate the effect of link weight quantization on the centrality measures in five types of real social networks. Consequently, we show that graphs with high skewness in their degree distribution and/or with high correlation between node degrees and link weights are robust against link weight quantization.

In this paper, we investigate the effectiveness of the records of user's activities in Twitter, which is a popular microblogging site, for estimating his/her depressive tendency. We construct multiple regression model to estimate user's depressive tendency from the frequencies of words used by the user. We perform experiments to estimate participants' depressive tendencies using the constructed regression model. Our experimental results show that there exists medium positive correlation (correlation coefficient r ≃ 0.45) between the Zung's Self-rating Depression Scale, which is a popular measure for estimating depressive tendency, and estimated score obtained from the regression model.

We propose a room-shaped information environment called Ambient Suite that enhances interpersonal communication. In Ambient Suite, the room itself works as both sensors to estimate the conversation states of participants and displays to present information to stimulate conversation. This paper introduces an implementation assumed standing-party situations as a typical use case of Ambient Suite. From the result of user study using its implementation, we confirmed that our system adequately encouraged participant conversations.

In this paper, we present our vision on large-scale and dynamic social network analysis in real environment, which is expected to be enabled by introduction of large-scale heterogeneous sensors in ambient environment. We address challenges toward realization of large-scale dynamic social network analysis in real environment, and discuss several promising applications. We finally present our preliminary experimental results of dynamic social network analysis for six-person social gatherings in real environment.