[go: up one dir, main page]

CN106027507B - The recognition methods of anonymous identity in a kind of social networks - Google Patents

The recognition methods of anonymous identity in a kind of social networks Download PDF

Info

Publication number
CN106027507B
CN106027507B CN201610308386.1A CN201610308386A CN106027507B CN 106027507 B CN106027507 B CN 106027507B CN 201610308386 A CN201610308386 A CN 201610308386A CN 106027507 B CN106027507 B CN 106027507B
Authority
CN
China
Prior art keywords
node
weight
user
nodes
similarity
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
CN201610308386.1A
Other languages
Chinese (zh)
Other versions
CN106027507A (en
Inventor
梁秀波
尹可挺
王宇凡
陈志民
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Zhejiang University ZJU
Original Assignee
Zhejiang University ZJU
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Zhejiang University ZJU filed Critical Zhejiang University ZJU
Priority to CN201610308386.1A priority Critical patent/CN106027507B/en
Publication of CN106027507A publication Critical patent/CN106027507A/en
Application granted granted Critical
Publication of CN106027507B publication Critical patent/CN106027507B/en
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Classifications

    • HELECTRICITY
    • H04ELECTRIC COMMUNICATION TECHNIQUE
    • H04LTRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L63/00Network architectures or network communication protocols for network security
    • H04L63/08Network architectures or network communication protocols for network security for authentication of entities
    • GPHYSICS
    • G06COMPUTING OR CALCULATING; COUNTING
    • G06QINFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q50/00Information and communication technology [ICT] specially adapted for implementation of business processes of specific business sectors, e.g. utilities or tourism
    • G06Q50/01Social networking
    • HELECTRICITY
    • H04ELECTRIC COMMUNICATION TECHNIQUE
    • H04LTRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00Routing or path finding of packets in data switching networks
    • H04L45/12Shortest path evaluation
    • H04L45/122Shortest path evaluation by minimising distances, e.g. by selecting a route with minimum of number of hops
    • HELECTRICITY
    • H04ELECTRIC COMMUNICATION TECHNIQUE
    • H04LTRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L63/00Network architectures or network communication protocols for network security
    • H04L63/04Network architectures or network communication protocols for network security for providing a confidential data exchange among entities communicating through data packet networks
    • H04L63/0407Network architectures or network communication protocols for network security for providing a confidential data exchange among entities communicating through data packet networks wherein the identity of one or more communicating identities is hidden
    • H04L63/0421Anonymous communication, i.e. the party's identifiers are hidden from the other party or parties, e.g. using an anonymizer

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Computing Systems (AREA)
  • Computer Security & Cryptography (AREA)
  • Signal Processing (AREA)
  • Business, Economics & Management (AREA)
  • General Engineering & Computer Science (AREA)
  • Computer Hardware Design (AREA)
  • General Health & Medical Sciences (AREA)
  • Primary Health Care (AREA)
  • Tourism & Hospitality (AREA)
  • Physics & Mathematics (AREA)
  • General Business, Economics & Management (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Strategic Management (AREA)
  • Marketing (AREA)
  • Human Resources & Organizations (AREA)
  • Economics (AREA)
  • Health & Medical Sciences (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

本发明公开了一种社交网络中匿名用户身份的识别方法,特点是具体步骤如下:(1)将已知用户的社交网络中抽象成无向图;计算出目标节点Vi与其他任一节点Vj之间的最短路径,并进一步计算出表示该已知用户与目标用户的关系强度的用户权值;(2)将另一包含目标匿名用户的社交网络图抽象成无向图,利用深度优先搜索计算其他任一已知节点到起点节点的权值,利用深度优先搜索法分别计算起点节点与未知节点的权值平均值;(3)通过搜索权值平均值差距最小的两个节点,从而识别出已知用户社交网络中的目标用户即为另一包含目标匿名用户社交网络中的目标匿名用户,优点是不仅能够识别匿名用户身份,同时匹配的准确率高。

The invention discloses a method for identifying anonymous user identities in a social network, which is characterized by the following specific steps: (1) abstracting the social network of known users into an undirected graph; calculating the target node Vi and any other node Vj (2) Abstract another social network graph containing the target anonymous user into an undirected graph, using depth-first search Calculate the weight from any other known node to the starting node, and use the depth-first search method to calculate the average weight of the starting node and the unknown node; (3) By searching for the two nodes with the smallest difference between the average weights, identify The target user in the social network of the known user is the target anonymous user in another social network containing the target anonymous user, which has the advantage of not only being able to identify the identity of the anonymous user, but also having a high matching accuracy.

Description

The recognition methods of anonymous identity in a kind of social networks
Technical field
The present invention relates to the recognition methods of user identity in social networks, use more particularly, to anonymous in a kind of social networks The recognition methods of family identity.
Background technique
There is a large amount of users in social networks, and the incidence relation between user and user to form between user One huge social networks.And it is all known to matching that the confirmation method of user identity is most of in existing social networks User account, specific steps are as follows: (1) their relationship environment is calculated according to each user account in two candidate social networks Scoring;(2) each account of one of social networks is matched with another social networks account, by calculating good friend Cohesion and non-good friend's degree of becoming estranged combine user environment to score to obtain respective end value;(3) each end value is ranked up; (4) user of the user account as final checked of highest scoring is selected.From the results of view, the prior art is built upon known Corresponding evaluation of estimate calculating is carried out on the basis of user and corresponding attribute value, this can no longer meet realization matching anonymous Demand because all properties value of anonymous be it is unknown, appraisement system can not be included in, be just more unable to get it Appraisal result value afterwards.
Summary of the invention
Technical problem to be solved by the invention is to provide a kind of accounts by known social networks to match difference Corresponding anonymous account in social networks, can not only identify anonymous identity, while the social network that matched accuracy rate is high The recognition methods of anonymous identity in network.
The technical scheme of the invention to solve the technical problem is: anonymous identity in a kind of social networks Recognition methods, the specific steps are as follows:
(1) user's weight computing in social networks known to
A. the pass in the social networks of known users, using user as the node with attribute, between user and user Social network diagram is abstracted into non-directed graph as the side between node and node by system;
B. in non-directed graph, using destination node Vi as starting point, other any nodes Vj is terminal, passes through dijkstra's algorithm The shortest path between destination node Vi and other any nodes Vj is calculated, the phase of all adjacent nodes on shortest path is calculated Like degree;
If C. other any nodes Vj and destination node Vi is connected directly, weighed using the similarity of two node as user Value;If other any nodes Vj is not connected directly with destination node Vi, with adjacent two nodes phase on the two nodes shortest path Like the tired similarity multiplied as any node Vj and destination node Vi of degree, using the similarity as user's weight;It obtains User's weight indicates the known users and the relationship strength of target user;
D. by the node for the user's weight being calculated with<destination node Vi, it is known that node Vj, weight>form composition knot Fruit collection output, obtains each user's weight in known social networks;
(2) weight computing in the social networks comprising target anonymous
A. in another social network diagram comprising target anonymous, using known users as the known section with attribute Point, unknown node of the anonymous as unknown properties, relationship between user and user as the side between node and node, Social network diagram is abstracted into non-directed graph;
B. choosing any known node is starting point node Wi, carries out depth-first search to other any known node Wj and obtains To corresponding weight, with<starting point node Wi, it is known that node Wj, weight>form composition result set output;
C. the respective distance value of starting point node Wi to all unknown node X is calculated separately using depth-first search, it will All distance values are added the number divided by unknown node X, obtain the weight average value of starting point node Wi and unknown node, with < rise Put node Wi, unknown node X, weight average value > form composition result set output;
(3) anonymous exports
A. known from the result set chosen in the result set in step (2) B in starting point node Wi attribute and step (1) D The identical each group of node Vj attribute, respectively by each group<starting point node Wi, it is known that node Wj, weight>in weight divided by<target Node Vi, it is known that node Vj, weight>in weight, each ratio is averaged, with<starting point node Wi, destination node Vi, power It is worth average value > form composition result set output;
B. obtained in general<starting point node Wi, destination node Vi, weight average value>and step (2) C<starting point node Wi, Unknown node X, weight average value > be compared search for weight average value difference away from the smallest two nodes, and destination node Vi is For unknown node X, so that it is another social comprising target anonymous for obtaining the target user in known users social networks Target anonymous in network, wherein i=1,2,3 ..., n, j=1,2,3 ..., n, the sum of i and j are all sections in non-directed graph Point number.
Step (1) interior joint similarity circular is as follows:
From destination node Vi to other any nodes Vj, along the direction of shortest path, with adjacent two nodes degree and subtract For one inverse as the similarity between adjacent two nodes, the similarity being calculated indicates the relationship strength between two users;Phase Neighbors calculating formula of similarity is as follows:
Compared with the prior art, the advantages of the present invention are as follows: it is used present invention firstly discloses anonymous in a kind of social networks The recognition methods of family identity, this method mainly experienced searching shortest path, weight meter in anonymous in identification process It calculates, matches three processes.
The shortest path stage is being found, the process employs dijkstra's algorithms.Using the algorithm, available two sections Shortest path between point, the node passed through on the shortest path of the node is more, and the result that similarity is tired out after multiplying is smaller, Weight is smaller.This demonstrate also smaller for the contribution of identification between the remoter node of distance.
Two kinds of situations: the node being connected directly with destination node are broadly divided into similarity calculation, not with destination node The node being connected directly.The node being wherein connected directly with target, with destination node and adjacent node degree and the inverse for subtracting one As the similarity of the two, and using the similarity as the weight of adjacent node.With destination node not direct neighbor node I By calculate on the shortest path between two nodes, the similarity of adjacent node, tired with these similarities multiply two-by-two As a result the weight as non-conterminous node.Fully ensure that node degree is bigger in this way, end value is smaller, and weight is smaller.It is commenting Value accurately on the basis of, recycle the obtained objective result of depth-first traversal algorithmic match, it is ensured that final matching knot The accuracy rate of fruit.
Detailed description of the invention
Fig. 1 is non-directed graph of the embodiment of the present invention.
Specific embodiment
The present invention will be described in further detail below with reference to the embodiments of the drawings.
Specific embodiment
The recognition methods of anonymous identity in a kind of social networks, the specific steps are as follows:
(1) user's weight computing in social networks known to
A. the pass in the social networks of known users, using user as the node with attribute, between user and user Social network diagram is abstracted into non-directed graph as the side between node and node by system;
B. in non-directed graph, using destination node Vi as starting point, other any nodes Vj is terminal, passes through dijkstra's algorithm The shortest path between destination node Vi and other any nodes Vj is calculated, the phase of all adjacent nodes on shortest path is calculated Like degree;Circular is as follows:
From destination node Vi to other any nodes Vj, along the direction of shortest path, with adjacent two nodes degree and subtract For one inverse as the similarity between adjacent two nodes, the similarity being calculated indicates the relationship strength between two users;Phase Neighbors calculating formula of similarity is as follows:
If C. other any nodes Vj and destination node Vi is connected directly, weighed using the similarity of two node as user Value;If other any nodes Vj is not connected directly with destination node Vi, with adjacent two nodes phase on the two nodes shortest path Like the tired similarity multiplied as any node Vj and destination node Vi of degree, using the similarity as user's weight;It obtains User's weight indicates the known users and the relationship strength of target user;
Such as illustrate the calculating of similarity between node by taking Fig. 1 non-directed graph as an example: with A, B, G, tetra- instruction manual users of F Similarity algorithm: there is no the paths to interlink between party A-subscriber and G user, therefore A, G similarity are 0, then the weight of G is 0;It is 1/ (1+3-1)=1/3 that A, B, which are connected directly then similarity, then the weight of B is 1/2;It is not connected directly between A, F user, But there are mulitpath A → B → F, A → B → C → E → F mulitpath.Selection is by most short between A to F in numerous paths Path A → B → F.Similarity between then A, B is 1/ (1+3-1)=1/3, and the similarity between B, F is 1/ (3+4-1) It is 1/18 that relationship strength between=1/6, then A, F, which is (1/3) * (1/6)=1/18, F weight,;
D. by the node for the user's weight being calculated with<destination node Vi, it is known that node Vj, weight>form composition knot Fruit collection output, obtains each user's weight in known social networks;
(2) weight computing in the social networks comprising target anonymous
A. in another social network diagram comprising target anonymous, using known users as the known section with attribute Point, unknown node of the anonymous as unknown properties, relationship between user and user as the side between node and node, Social network diagram is abstracted into non-directed graph;
B. choosing any known node is starting point node Wi, carries out depth-first search to other any known node Wj and obtains To corresponding weight (the same above-mentioned steps of weight calculation method (1)), with<starting point node Wi, it is known that node Wj, weight>form group It is exported at result set;
C. the respective distance value of starting point node Wi to all unknown node X is calculated separately using depth-first search, it will All distance values are added the number divided by unknown node X, obtain the weight average value of starting point node Wi and unknown node, with < rise Put node Wi, unknown node X, weight average value > form composition result set output;
(3) anonymous exports
A. known from the result set chosen in the result set in step (2) B in starting point node Wi attribute and step (1) D The identical each group of node Vj attribute, respectively by each group<starting point node Wi, it is known that node Wj, weight>in weight divided by<target Node Vi, it is known that node Vj, weight>in weight, each ratio is averaged, with<starting point node Wi, destination node Vi, power It is worth average value > form composition result set output;
B. obtained in general<starting point node Wi, destination node Vi, weight average value>and step (2) C<starting point node Wi, Unknown node X, weight average value > be compared search for weight average value difference away from the smallest two nodes, and destination node Vi is For unknown node X, so that it is another social comprising target anonymous for obtaining the target user in known users social networks Target anonymous in network, wherein i=1,2,3 ..., n, j=1,2,3 ..., n, the sum of i and j are all sections in non-directed graph Point number.
This method different nodes in the identification process of anonymous are played the role of difference, not for quantitative description With node in anonymous recognitive engineering made contribution, we assign different weights for each node.Weight it is big It is small to have reacted the node contribution in later period identification work.And the size of weight is mainly influenced by following several respects: with The distance of anonymous to be identified, the quantity (representative is user good friend quantity) of node degree, with anonymous to be identified The factors such as intimate degree influence.Among these factors, closer apart from anonymous, it is more intimate with anonymous, in identification user Play the role of bigger when identity, corresponding weight is also bigger, and the quantity of node degree is bigger, the tribute when identifying user identity Offer it is smaller, weight also just it is smaller.Therefore, this method proposes to carry out the similarity between calculate node using node similarity algorithm, And using the value of similarity as the weight of the node.This method adjacent node degree and subtract one in node similarity algorithm Similarity reciprocal as two nodes, it ensure that degree is bigger (friend is more), node similarity is lower (weight is smaller).And And use the tired result multiplied as the similarity of non-conterminous node, since similarity is respectively less than 1, distance it is remoter it is tired multiply it is more, then Similarity is smaller (weight is smaller).It ensure that the remoter node of distance, contribution degree are also smaller.Thus the algorithm is adequately examined The problem of having considered node degree and node and anonymous apart from the problem of.It is bigger to be truly realized degree, the remoter section of distance The weight of point is smaller.On the basis of evaluation of estimate is accurate, the objective result for recycling depth-first traversal algorithmic match to obtain can To guarantee the accuracy rate of final matching results.
Certainly, above description is not limitation of the present invention, and the present invention is also not limited to the example above.The art The variations, modifications, additions or substitutions that those of ordinary skill makes within the essential scope of the present invention also should belong to protection of the present invention Range.

Claims (2)

1. the recognition methods of anonymous identity in a kind of social networks, it is characterised in that specific step is as follows:
(1) user's weight computing in social networks known to
A. in the social networks of known users, using user as the node with attribute, the relationship between user and user is made Social network diagram is abstracted into non-directed graph by the side between node and node;
B. in non-directed graph, using destination node Vi as starting point, other any nodes Vj is terminal, is calculated by dijkstra's algorithm Shortest path between destination node Vi and other any nodes Vj out, calculate shortest path on all adjacent nodes it is similar Degree;
If C. other any nodes Vj and destination node Vi is connected directly, using the similarity of two node as user's weight; If other any nodes Vj is not connected directly with destination node Vi, with adjacent two nodes similarity on the two nodes shortest path The tired similarity multiplied as any node Vj and destination node Vi, using the similarity as user's weight;Obtained user Weight indicates the known users and the relationship strength of target user;
D. by the node for the user's weight being calculated with<destination node Vi, it is known that node Vj, weight>form form result set Output obtains each user's weight in known social networks;
(2) weight computing in the social networks comprising target anonymous
A. in another social network diagram comprising target anonymous, using known users as with attribute known node, Unknown node of the anonymous as unknown properties, the relationship between user and user, will as the side between node and node Social network diagram is abstracted into non-directed graph;
B. choosing any known node is starting point node Wi, carries out depth-first search to other any known node Wj and obtains phase The weight answered, with<starting point node Wi, it is known that node Wj, weight>form composition result set output;
C. starting point node Wi is calculated separately to the respective distance value of all unknown node X using depth-first search, will own Distance value is added the number divided by unknown node X, the weight average value of starting point node Wi and unknown node is obtained, with < starting point section Point Wi, unknown node X, weight average value > form composition result set output;
(3) anonymous exports
A. the known node from the result set chosen in the result set in step (2) B in starting point node Wi attribute and step (1) D The identical each group of Vj attribute, respectively by each group<starting point node Wi, it is known that node Wj, weight>in weight divided by<destination node Vi, it is known that node Vj, weight>in weight, each ratio is averaged, with<starting point node Wi, destination node Vi, weight is flat Mean value > form composition result set output;
B. general<starting point node Wi, destination node Vi, weight average value>with obtained in step (2) C<starting point node Wi, it is unknown Nodes X, weight average value > be compared, for search weight average value difference away from the smallest two nodes, destination node Vi is not Nodes X is known, so that obtaining the target user in known users social networks is another comprising target anonymous social networks In target anonymous, wherein i=1,2,3 ..., n, j=1,2,3 ..., n, the sum of i and j are all nodes in non-directed graph Number.
2. the recognition methods of anonymous identity in a kind of social networks according to claim 1, it is characterised in that step (1) interior joint similarity circular is as follows:
From destination node Vi to other any nodes Vj, along the direction of shortest path, with adjacent two nodes degree and subtract one For inverse as the similarity between adjacent two nodes, the similarity being calculated indicates the relationship strength between two users;Adjacent segments Point calculating formula of similarity is as follows:
Wherein sim symbol indicate two nodes it Between similarity, similarity indicates the relationship strength between two users;Degree symbol indicates that the degree of present node, degree refer to Be present node number of branches.
CN201610308386.1A 2016-05-11 2016-05-11 The recognition methods of anonymous identity in a kind of social networks Expired - Fee Related CN106027507B (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201610308386.1A CN106027507B (en) 2016-05-11 2016-05-11 The recognition methods of anonymous identity in a kind of social networks

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201610308386.1A CN106027507B (en) 2016-05-11 2016-05-11 The recognition methods of anonymous identity in a kind of social networks

Publications (2)

Publication Number Publication Date
CN106027507A CN106027507A (en) 2016-10-12
CN106027507B true CN106027507B (en) 2019-03-26

Family

ID=57099961

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201610308386.1A Expired - Fee Related CN106027507B (en) 2016-05-11 2016-05-11 The recognition methods of anonymous identity in a kind of social networks

Country Status (1)

Country Link
CN (1) CN106027507B (en)

Families Citing this family (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN108171612A (en) * 2016-12-06 2018-06-15 北京国双科技有限公司 A kind of correlating method and device
CN106960391A (en) * 2017-02-23 2017-07-18 武汉智寻天下科技有限公司 A kind of user profile polymerization, system and device
CN107945037A (en) * 2017-11-27 2018-04-20 北京工商大学 A kind of social networks based on node structure feature goes de-identification method
CN110046747B (en) * 2019-03-19 2021-07-27 华中科技大学 A graph flow-oriented path planning method and system among social network users
CN111371611B (en) * 2020-02-28 2021-06-25 广州大学 A deep learning-based weighted network community discovery method and device

Family Cites Families (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8290981B2 (en) * 2011-03-08 2012-10-16 Hon Hai Precision Industry Co., Ltd. Social network system and member searching and analyzing method in social network
US10521473B2 (en) * 2012-05-21 2019-12-31 Kent State University Shortest path computation in large networks
CN105117443B (en) * 2015-08-12 2018-07-20 华南理工大学 A kind of proposed algorithm based on more relational networks
CN105528407B (en) * 2015-12-04 2021-12-14 杭州师范大学 A method and device for obtaining L users with the best spreading influence

Also Published As

Publication number Publication date
CN106027507A (en) 2016-10-12

Similar Documents

Publication Publication Date Title
CN106027507B (en) The recognition methods of anonymous identity in a kind of social networks
CN107482626B (en) A method for identifying key nodes in regional power grid
Jahan et al. A target-based normalization technique for materials selection
CN110110094A (en) Across a network personage&#39;s correlating method based on social networks knowledge mapping
Bergamini et al. Fully-dynamic approximation of betweenness centrality
CN104778213B (en) A kind of social networks recommendation method based on random walk
CN110601173B (en) Method and device for identification of distribution network topology based on edge computing
US20130110835A1 (en) Method for calculating proximities between nodes in multiple social graphs
CN104915418A (en) Website recommendation method and device
CN107945037A (en) A kind of social networks based on node structure feature goes de-identification method
CN103500168A (en) Method and system for discovering communities in overlapped complex networks according to topology potential
JP7092194B2 (en) Information processing equipment, judgment method, and program
CN108614897A (en) A kind of contents diversification searching method towards natural language
CN103337028A (en) Recommendation method and device
CN111061624A (en) Policy execution effect determination method and device, electronic equipment and storage medium
Ahmed et al. Restaurant recommendation system in Dhaka city using machine learning approach
CN110309864B (en) Collaborative filtering recommendation method fusing local similarity and global similarity
CN107506488A (en) A kind of intelligent music commending system
CN105719190A (en) Social network node influence measuring method based on triangle structures
CN109085513A (en) A kind of method and apparatus that the internal resistance of cell calculates
CN107688658A (en) The localization method and device of a kind of abnormal data
Hayat On generalized atom-bond connectivity index of cacti
Freitas et al. Identifying influential patents in citation networks using enhanced VoteRank centrality
Wang et al. Examination of multi-objective optimization method for global search using DIRECT and GA
CN103955545B (en) A kind of personalized social network influence recognition methods

Legal Events

Date Code Title Description
C06 Publication
PB01 Publication
C10 Entry into substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant
CF01 Termination of patent right due to non-payment of annual fee
CF01 Termination of patent right due to non-payment of annual fee

Granted publication date: 20190326