Dynamic publishing of social network graphs offers insights into user behavior but brings privacy risks, notably re-identification attacks on evolving data snapshots. Existing methods based on -anonymity can mitigate ...Dynamic publishing of social network graphs offers insights into user behavior but brings privacy risks, notably re-identification attacks on evolving data snapshots. Existing methods based on -anonymity can mitigate these attacks but are cumbersome, neglect dynamic protection of community structure, and lack precise utility measures. To address these challenges, we present a dynamic social network graph anonymity scheme with community structure protection (DSNGA-CSP), which achieves the dynamic anonymization process by incorporating community detection. First, DSNGA-CSP categorizes communities of the original graph into three types at each timestamp, and only partitions community subgraphs for a specific category at each updated timestamp. Then, DSNGA-CSP achieves intra-community and inter-community anonymization separately to retain more of the community structure of the original graph at each timestamp. It anonymizes community subgraphs by the proposed novel -composition method and anonymizes inter-community edges by edge isomorphism. Finally, a novel information loss metric is introduced in DSNGA-CSP to precisely capture the utility of the anonymized graph through original information preservation and anonymous information changes. Extensive experiments conducted on five real-world datasets demonstrate that DSNGA-CSP consistently outperforms existing methods, providing a more effective balance between privacy and utility. Specifically, DSNGA-CSP shows an average utility improvement of approximately 30% compared to TAKG and CTKGA for three dynamic graph datasets, according to the proposed information loss metric IL.展开更多
The goal of privacy-preserving social graph release is to protect individual privacy while preserving data util-ity.Community structure,which is an important global pattern of nodes,is a crucial data utility as it is ...The goal of privacy-preserving social graph release is to protect individual privacy while preserving data util-ity.Community structure,which is an important global pattern of nodes,is a crucial data utility as it is fundamental to many graph analysis tasks.Yet,most existing methods with differential privacy(DP)commonly fall into edge-DP to sacri-fice security in exchange for utility.Moreover,they reconstruct graphs from the local feature-extraction of nodes,resulting in poor community preservation.Motivated by this,we develop PrivCom,a strict node-DP graph release algorithm to maximize the utility on the community structure while maintaining a higher level of privacy.In this algorithm,to reduce the huge sensitivity,we devise a Katz index based private graph feature extraction method,which can capture global graph structure features while greatly reducing the global sensitivity via a sensitivity regulation strategy.Yet,under the condition that the sensitivity is fixed,the feature captured by the Katz index,which is presented in matrix form,requires privacy budget splits.As a result,plenty of noise is injected,mitigating global structural utility.To bridge this gap,we de-sign a private eigenvector estimation method,which yields noisy eigenvectors from extracted low-dimensional vectors.Then,a dynamic privacy budget allocation method with provable utility guarantees is developed to preserve the inherent relationship between eigenvalues and eigenvectors,so that the utility of the generated noise Katz matrix is well main-tained.Finally,we reconstruct the synthetic graph via calculating its Laplacian with the noisy Katz matrix.Experimental results confirm our theoretical findings and the efficacy of PrivCom.展开更多
The advent of the time of big data along with social networks makes the visualization and analysis of networks information become increasingly important in many fields. Based on the information from social networks, t...The advent of the time of big data along with social networks makes the visualization and analysis of networks information become increasingly important in many fields. Based on the information from social networks, the idea of information visualization and development of tools are presented. Popular social network micro-blog （＇Weibo＇） is chosen to realize the process of users＇ interest and communications data analysis. User interest visualization methods are discussed and chosen and programs are developed to collect users＇ interest and describe it by graph. The visualization results may be used to provide the commercial recommendation or social investigation application for decision makers.展开更多
The introduction of the social networking platform has drastically affected the way individuals interact. Even though most of the effects have been positive, there exist some serious threats associated with the intera...The introduction of the social networking platform has drastically affected the way individuals interact. Even though most of the effects have been positive, there exist some serious threats associated with the interactions on a social networking website. A considerable proportion of the crimes that occur are initiated through a social networking platform [1]. Almost 33% of the crimes on the internet are initiated through a social networking website [1]. Moreover activities like spam messages create unnecessary traffic and might affect the user base of a social networking platform. As a result preventing interactions with malicious intent and spam activities becomes crucial. This work attempts to detect the same in a social networking platform by considering a social network as a weighted graph wherein each node, which represents an individual in the social network, stores activities of other nodes with respect to itself in an optimized format which is referred to as localized data set. The weights associated with the edges in the graph represent the trust relationship between profiles. The weights of the edges along with the localized data set are used to infer whether nodes in the social network are compromised and are performing spam or malicious activities.展开更多
This paper proposes an analytical mining tool for big graph data based on MapReduce and bulk synchronous parallel （BSP） com puting model. The tool is named Mapreduce and BSP based Graphmining tool （MBGM）. The core...This paper proposes an analytical mining tool for big graph data based on MapReduce and bulk synchronous parallel （BSP） com puting model. The tool is named Mapreduce and BSP based Graphmining tool （MBGM）. The core of this mining system are four sets of parallel graphmining algorithms programmed in the BSP parallel model and one set of data extractiontransformationload ing （ETE） algorithms implemented in MapReduce. To invoke these algorithm sets, we designed a workflow engine which optimized for cloud computing. Finally, a welldesigned data management function enables users to view, delete and input data in the Ha doop distributed file system （HDFS）. Experiments on artificial data show that the components of graphmining algorithm in MBGM are efficient.展开更多
Using Kripke semantics, we have identified and reduced an epistemic incompleteness in the metaphor commonly employed in Social Networks Analysis (SNA), which basically compares information flows with current flows in ...Using Kripke semantics, we have identified and reduced an epistemic incompleteness in the metaphor commonly employed in Social Networks Analysis (SNA), which basically compares information flows with current flows in advanced centrality measures. Our theoretical approach defines a new paradigm for the semantic and dynamic analysis of social networks including shared content. Based on our theoretical findings, we define a semantic and predictive model of dynamic SNA for Enterprises Social Networks (ESN), and experiment it on a real dataset.展开更多
With the growth of the internet it is becoming increasingly important to understand how the behaviour of players is affected by the topology of the network interconnecting them. Many models which involve networks of i...With the growth of the internet it is becoming increasingly important to understand how the behaviour of players is affected by the topology of the network interconnecting them. Many models which involve networks of interacting players have been proposed and best response games are amongst the simplest. In best response games each vertex simultaneously updates to employ the best response to their current surroundings. We concentrate upon trying to understand the dynamics of best response games on regular graphs with many strategies. When more than two strategies are present highly complex dynamics can ensue. We focus upon trying to understand exactly how best response games on regular graphs sample from the space of possible cellular automata. To understand this issue we investigate convex divisions in high dimensional space and we prove that almost every division of k - 1 dimensional space into k convex regions includes a single point where all regions meet. We then find connections between the convex geometry of best response games and the theory of alternating circuits on graphs. Exploiting these unexpected connections allows us to gain an interesting answer to our question of when cellular automata are best response games.展开更多
基金supported by the Natural Science Foundation of China(No.U22A2099)the Innovation Project of Guangxi Graduate Education(YCBZ2023130).
文摘Dynamic publishing of social network graphs offers insights into user behavior but brings privacy risks, notably re-identification attacks on evolving data snapshots. Existing methods based on -anonymity can mitigate these attacks but are cumbersome, neglect dynamic protection of community structure, and lack precise utility measures. To address these challenges, we present a dynamic social network graph anonymity scheme with community structure protection (DSNGA-CSP), which achieves the dynamic anonymization process by incorporating community detection. First, DSNGA-CSP categorizes communities of the original graph into three types at each timestamp, and only partitions community subgraphs for a specific category at each updated timestamp. Then, DSNGA-CSP achieves intra-community and inter-community anonymization separately to retain more of the community structure of the original graph at each timestamp. It anonymizes community subgraphs by the proposed novel -composition method and anonymizes inter-community edges by edge isomorphism. Finally, a novel information loss metric is introduced in DSNGA-CSP to precisely capture the utility of the anonymized graph through original information preservation and anonymous information changes. Extensive experiments conducted on five real-world datasets demonstrate that DSNGA-CSP consistently outperforms existing methods, providing a more effective balance between privacy and utility. Specifically, DSNGA-CSP shows an average utility improvement of approximately 30% compared to TAKG and CTKGA for three dynamic graph datasets, according to the proposed information loss metric IL.
基金A preliminary version of the paper was published in the Proceedings of ICDM 2020supported by the National Natural Science Foundation of China under Grant No.61772131the Science and Technology Project of the State Grid Corporation of China under Grant No.5700-202018268A-0-0-00.
文摘The goal of privacy-preserving social graph release is to protect individual privacy while preserving data util-ity.Community structure,which is an important global pattern of nodes,is a crucial data utility as it is fundamental to many graph analysis tasks.Yet,most existing methods with differential privacy(DP)commonly fall into edge-DP to sacri-fice security in exchange for utility.Moreover,they reconstruct graphs from the local feature-extraction of nodes,resulting in poor community preservation.Motivated by this,we develop PrivCom,a strict node-DP graph release algorithm to maximize the utility on the community structure while maintaining a higher level of privacy.In this algorithm,to reduce the huge sensitivity,we devise a Katz index based private graph feature extraction method,which can capture global graph structure features while greatly reducing the global sensitivity via a sensitivity regulation strategy.Yet,under the condition that the sensitivity is fixed,the feature captured by the Katz index,which is presented in matrix form,requires privacy budget splits.As a result,plenty of noise is injected,mitigating global structural utility.To bridge this gap,we de-sign a private eigenvector estimation method,which yields noisy eigenvectors from extracted low-dimensional vectors.Then,a dynamic privacy budget allocation method with provable utility guarantees is developed to preserve the inherent relationship between eigenvalues and eigenvectors,so that the utility of the generated noise Katz matrix is well main-tained.Finally,we reconstruct the synthetic graph via calculating its Laplacian with the noisy Katz matrix.Experimental results confirm our theoretical findings and the efficacy of PrivCom.
文摘The advent of the time of big data along with social networks makes the visualization and analysis of networks information become increasingly important in many fields. Based on the information from social networks, the idea of information visualization and development of tools are presented. Popular social network micro-blog （＇Weibo＇） is chosen to realize the process of users＇ interest and communications data analysis. User interest visualization methods are discussed and chosen and programs are developed to collect users＇ interest and describe it by graph. The visualization results may be used to provide the commercial recommendation or social investigation application for decision makers.
文摘The introduction of the social networking platform has drastically affected the way individuals interact. Even though most of the effects have been positive, there exist some serious threats associated with the interactions on a social networking website. A considerable proportion of the crimes that occur are initiated through a social networking platform [1]. Almost 33% of the crimes on the internet are initiated through a social networking website [1]. Moreover activities like spam messages create unnecessary traffic and might affect the user base of a social networking platform. As a result preventing interactions with malicious intent and spam activities becomes crucial. This work attempts to detect the same in a social networking platform by considering a social network as a weighted graph wherein each node, which represents an individual in the social network, stores activities of other nodes with respect to itself in an optimized format which is referred to as localized data set. The weights associated with the edges in the graph represent the trust relationship between profiles. The weights of the edges along with the localized data set are used to infer whether nodes in the social network are compromised and are performing spam or malicious activities.
基金supported by ZTE Industry-Academia-Research Cooperaton Funds
文摘This paper proposes an analytical mining tool for big graph data based on MapReduce and bulk synchronous parallel （BSP） com puting model. The tool is named Mapreduce and BSP based Graphmining tool （MBGM）. The core of this mining system are four sets of parallel graphmining algorithms programmed in the BSP parallel model and one set of data extractiontransformationload ing （ETE） algorithms implemented in MapReduce. To invoke these algorithm sets, we designed a workflow engine which optimized for cloud computing. Finally, a welldesigned data management function enables users to view, delete and input data in the Ha doop distributed file system （HDFS）. Experiments on artificial data show that the components of graphmining algorithm in MBGM are efficient.
文摘Using Kripke semantics, we have identified and reduced an epistemic incompleteness in the metaphor commonly employed in Social Networks Analysis (SNA), which basically compares information flows with current flows in advanced centrality measures. Our theoretical approach defines a new paradigm for the semantic and dynamic analysis of social networks including shared content. Based on our theoretical findings, we define a semantic and predictive model of dynamic SNA for Enterprises Social Networks (ESN), and experiment it on a real dataset.
文摘With the growth of the internet it is becoming increasingly important to understand how the behaviour of players is affected by the topology of the network interconnecting them. Many models which involve networks of interacting players have been proposed and best response games are amongst the simplest. In best response games each vertex simultaneously updates to employ the best response to their current surroundings. We concentrate upon trying to understand the dynamics of best response games on regular graphs with many strategies. When more than two strategies are present highly complex dynamics can ensue. We focus upon trying to understand exactly how best response games on regular graphs sample from the space of possible cellular automata. To understand this issue we investigate convex divisions in high dimensional space and we prove that almost every division of k - 1 dimensional space into k convex regions includes a single point where all regions meet. We then find connections between the convex geometry of best response games and the theory of alternating circuits on graphs. Exploiting these unexpected connections allows us to gain an interesting answer to our question of when cellular automata are best response games.
