CN106570082B - A kind of friends method for digging of combination network topology characteristic and user behavior characteristics - Google Patents
A kind of friends method for digging of combination network topology characteristic and user behavior characteristics Download PDFInfo
- Publication number
- CN106570082B CN106570082B CN201610907676.8A CN201610907676A CN106570082B CN 106570082 B CN106570082 B CN 106570082B CN 201610907676 A CN201610907676 A CN 201610907676A CN 106570082 B CN106570082 B CN 106570082B
- Authority
- CN
- China
- Prior art keywords
- user
- taste
- restaurant
- follows
- corporations
- 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.)
- Active
Links
- 238000000034 method Methods 0.000 title claims abstract description 24
- 230000003542 behavioural effect Effects 0.000 claims abstract description 10
- 238000012549 training Methods 0.000 claims abstract description 8
- 238000001514 detection method Methods 0.000 claims abstract description 5
- 238000012360 testing method Methods 0.000 claims abstract description 5
- 235000019640 taste Nutrition 0.000 claims description 31
- 239000011159 matrix material Substances 0.000 claims description 28
- 238000010606 normalization Methods 0.000 claims description 13
- YKFRUJSEPGHZFJ-UHFFFAOYSA-N N-trimethylsilylimidazole Chemical compound C[Si](C)(C)N1C=CN=C1 YKFRUJSEPGHZFJ-UHFFFAOYSA-N 0.000 claims description 3
- 238000004220 aggregation Methods 0.000 claims 1
- 230000002776 aggregation Effects 0.000 claims 1
- 230000006399 behavior Effects 0.000 description 16
- 238000009412 basement excavation Methods 0.000 description 3
- 235000013399 edible fruits Nutrition 0.000 description 2
- 238000013468 resource allocation Methods 0.000 description 2
- 240000000233 Melia azedarach Species 0.000 description 1
- 206010034719 Personality change Diseases 0.000 description 1
- 238000012512 characterization method Methods 0.000 description 1
- 238000007418 data mining Methods 0.000 description 1
- 230000007812 deficiency Effects 0.000 description 1
- 238000011161 development Methods 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 235000013305 food Nutrition 0.000 description 1
- 235000012054 meals Nutrition 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/90—Details of database functions independent of the retrieved data types
- G06F16/95—Retrieval from the web
- G06F16/953—Querying, e.g. by the use of web search engines
- G06F16/9535—Search customisation based on user profiles and personalisation
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06Q—INFORMATION 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/00—Information and communication technology [ICT] specially adapted for implementation of business processes of specific business sectors, e.g. utilities or tourism
- G06Q50/01—Social networking
Landscapes
- Engineering & Computer Science (AREA)
- Databases & Information Systems (AREA)
- Theoretical Computer Science (AREA)
- Business, Economics & Management (AREA)
- General Physics & Mathematics (AREA)
- Physics & Mathematics (AREA)
- Primary Health Care (AREA)
- Marketing (AREA)
- Human Resources & Organizations (AREA)
- Strategic Management (AREA)
- Tourism & Hospitality (AREA)
- General Health & Medical Sciences (AREA)
- General Business, Economics & Management (AREA)
- Economics (AREA)
- Health & Medical Sciences (AREA)
- Computing Systems (AREA)
- Data Mining & Analysis (AREA)
- General Engineering & Computer Science (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
A kind of friends method for digging of combination network topology characteristic and user behavior characteristics, comprising the following steps: 1) establish friendship network figure, the friends for randomly selecting wherein 90% connects number of edges according to being training set, and remaining 10% is used as test set；2) non-directed graph of having the right of two kinds of friendship networks based on topological similarity is constructed；3) non-directed graph of having the right of two kinds of friendship networks based on user behavior characteristics similarity is constructed；4) community division is carried out to above-mentioned four kinds non-directed graphs of having the right respectively using corporations' detection algorithm (CNM algorithm) based on weighting block degree, if any two user is at least divided into the same community three times or above during above-mentioned four kinds of community divisions, then it is assumed that the two users are friends.Topological characteristic and behavioural characteristic are introduced into user friend's relational network by the present invention, by community division, excavate whether two users are friends.
Description
Technical field
The present invention relates to data mining and recommender system field, more particularly to one kind based on social networks topological characteristic with
And the friends method for digging of user behavior characteristics.
Background technique
With the rise of internet especially mobile Internet, valuable information is excavated in the information and data of magnanimity
It is presented to the user, becomes the core function of major mainstream applications such as electric business, social activity, news, audio-visual.Recommender system especially individual character
Change is recommended as every user and provides precisely, in time, even has the individual info service of pleasantly surprised sense, either for
Greatly value for the product for still issuing the function, is all hidden in family.And friend prediction have for a user it is different
The pleasantly surprised sense of sample, because if Products Show has gone out the friend in your reality, and originally and your good friend is not present in these friends
In list, user can greatly improve the good opinion to the product, loyalty, this is most important to the development of product.This hair
The bright friends for excavating " potential " for being maximum possible recommends user.
Summary of the invention
It, can only in order to overcome friendship network traditional in existing social networks that can be abstracted as undirected no weight graph
Indicate whether be between the two there are friends, can not effectively excavate the deficiency of friends, the present invention by network characterization with
And user behavior characteristics are introduced into traditional friendship network, not only indicate whether the two is friend, can also indicate two
The degree of strength of friends considers the similarity of two people, i.e. social networks topological characteristic and user from different angles
Behavioural characteristic carries out community division using improved CNM (Clauset-Newman-Moore) algorithm, exists between men
The phenomenon that " Things of a kind come together ", present invention combination network topology characteristic and user behavior characteristics are calculated using improved CNM
Method excavates two users with the presence or absence of friends.
The technical solution adopted by the present invention to solve the technical problems is as follows:
A kind of friends method for digging of combination network topology characteristic and user behavior characteristics, the method for digging include
Following steps:
S1: it includes friend networks and have dinner place, taste information that data set, which provides, initially sets up friendship network figure,
The friends for randomly selecting wherein setting ratio connects number of edges according to being training set, and remainder is as test set；
S2: friends is established according to training set and haves no right non-directed graph G1=(V, E1), scheme G1Adjacency matrix A=
(aij)v×v, i, j ∈ { 1,2 ..., v }, in which:
According to adjacency matrix Av×v=(aij)v×v, i, j ∈ 1,2 ..., and v } the following two kinds network topology spy is found out respectively
Sign: resource allocation index (RA), Jaccard index (J) respectively obtain following each topological characteristic matrix:
RAv×v=(RAij)v×v,Jv×v=(Jij)v×v, i, j ∈ { 1,2 ..., v } the following is each eigenmatrix element expression
Formula:
Wherein Γ (i) be node i neighbor node set, k (z)=| Γ (z) | be node z degree, each eigenmatrix
RAv×v, Jv×vLinear normalization is respectivelyEach element expression formula is as follows in above-mentioned matrix:
As above friends is had no right into non-directed graph G1Two kinds of non-directed graphs of having the right are separately converted to, wherein weight is respectively equal to
The value of eigenmatrix after above two normalization, i.e.,
S3: by the record data in user existing have dinner place and taste behavior, two class bipartite graphs are established respectively, that is, are used
Family-restaurant area, user-taste label, process are as follows: defining restaurant bipartite graph G=(X, E, R), wherein Xi={ x1,
x2,...,xv, i ∈ { 1,2 ..., v } indicates v user, Ri={ r1,r2,...,rn, i ∈ { 1,2 ..., n } indicates n meal
Shop, if user xi, i ∈ 1,2 ..., and v } removed restaurant rj, j ∈ { 1,2 ..., n }, then with have the right even side indicate that the user goes
The restaurant several times, weight dij, i ∈ { 1,2 ..., v }, j ∈ { 1,2 ..., n }, that is, the number gone, similarly, building user-
Taste label bipartite graph G (X, E', T), wherein Xi={ x1,x2,...,xv, i ∈ { 1,2 ..., v } indicates v user, Ti=
{t1,t2,...,tm, i ∈ { 1,2 ..., m } indicates m taste label, if user xiSelect taste tj, j ∈ { 1,2 ..., m },
Then indicate that the user has selected the taste several times, weight d with even side of having the righti'j,i∈{1,2,...,v},j∈{1,2,...,
M }, i.e. the number of selection；The S3 the following steps are included:
S3-1: respectively according to user-restaurant and user-taste label bipartite graph, the section of any two user is calculated
Point similarity, for characterizing the behavioral difference between two users, wherein dijIndicate user xiRemove restaurant rjNumber, then user
xiRemove restaurant rjProbability are as follows:
Wherein, k=1,2 ..., | v | indicate all users；
According to the definition of uncorrelated entropy, restaurant rjEntropy are as follows:
Wherein, EjIt is worth bigger, expression restaurant rjIt is more popular with users；
User xi,xjSelect the characteristic similarity (RSIM) in restaurant is defined as:
EigenmatrixEach element linear normalization result are as follows:
Similarly, in user-taste label bipartite graph, di'jIndicate user xiTasted taste tjNumber, then user xiIt tastes
Cross taste tjProbability are as follows:
According to the definition of uncorrelated entropy, taste tjEntropy are as follows:
Wherein, E 'ijIt is worth bigger, expression taste tjIt is more popular with users；
Then user selects similarity feature (TSIM of the restaurant on tasteij) is defined as:
EigenmatrixEach element linear normalization result are as follows:
S3-2: according to the friend networks that rebuild of above two user behavior characteristics, that is, have the right non-directed graph G2=(V,
E2), process is as follows: retaining user node, deletes all friends and connect side, whether has Lian Bian between two o'clock and even the weight on side takes
Certainly in user behavior characteristics similarity, the wherein company side E of friend networks2Weight be taken respectively from above-mentioned two eigenmatrix i.e.
S4: corporations are carried out to aforementioned four non-directed graph of having the right respectively using corporations' detection algorithm based on weighting block degree and are drawn
Point, it the following is the modularity formula of weighting Undirected networks are as follows:
Wherein, W is the weights sum on all sides in network, siIt is the intensity of node, i.e., all sides being connected with node i
Weight and wijIt is the weight on the company side between nodes i and node j, sisj/ (2W) is corresponding zero model interior joint i
The desired weight on the company side between node j, CiWith CjRespectively indicate node i and node j in a network belonging to corporations: such as
The two nodes of fruit belong to same corporations, then δ (Ci,Cj)=1；Otherwise value be 0, the S4 the following steps are included:
S4-1: initialization: assume that each node is exactly an independent corporations when initial, i.e. v corporations, selection is based onNon-directed graph of having the right be object, the weights sum on all sides of the network is W1, module angle value Q=0, defines symmetrical square at this time
Battle array Fv×v, element f thereinijIndicate that the side right value in connection corporations and corporations accounts for the ratio of all side right values；Definition line adds
AlwaysIt indicates that the side right value of all nodes being connected in corporations accounts for the ratio of total weight value, matrix F and auxiliary vectorElement be fijAnd ai, initial fij、aiIt calculates as follows:
ai=si/(2W1)
Wherein, fijNonzero value be according to be based on different characteristic i.e. topological characteristic, behavioural characteristic non-directed graph of having the right
Object determines that each element of initial modularity Increment Matrix Δ Q calculates as follows:
After obtaining initial module Increment Matrix, the most raft H being made of the greatest member of its every a line can be obtained；
S4-2: max { Δ Q is selected from most raft Hij, merge corresponding corporations GiAnd Gj, corporations' mark after label merging
Number be j；And update module degree Increment Matrix Δ Q, most raft H and auxiliary vector
S4-2-1: the update of Δ Q: deleting the element of the i-th row and the i-th column, updates the element of jth row and jth column, obtains
S4-2-2: the most update of raft H: after updating Δ Q, the greastest element of corresponding row and column in Yao Gengxin most raft
Element；
S4-2-3: auxiliary vectorUpdate it is as follows:
aj←ai+aj, then ai=0
And it records and merges later module angle value:
Q←Q+max{ΔQij}
S4-2-4: step S4-2-2 is repeated until node all in network is all grouped into a corporations；
When element maximum in modularity Increment Matrix is from just becoming negative, just stop merging, and thinks result at this time just
It is to be based onNon-directed graph network of having the right community structure C1；
S4-3: selection is based onHave the right Undirected networks be object, repeat S4-1 process, can obtain
To being based onUndirected networks of having the right community structure C2,C3,C4；
S4-4: according to the network society for above based on four kinds of different characteristics including network topology characteristic and user behavior characteristics
Unity structure, i.e. C1,C2,C3,C4If any two user two o'clock during above-mentioned four kinds of community divisions at least three times or
Divided into the same community above, then it is assumed that the two users are friends.
The invention has the benefit that the present invention excavates the customer relationship in social networks (i.e. in customer relationship network not
The company's side state known), final prediction result is higher, can effectively meet the requirement of actual use.
Detailed description of the invention
Fig. 1 is the flow chart of the customer relationship method of excavation in the social networks of the embodiment of the present invention.
Specific embodiment
The present invention will be further described with reference to the accompanying drawing.
Referring to Fig.1, the friends method for digging of a kind of combination network topology characteristic and user behavior characteristics, the excavation
Method the following steps are included:
S1: according to Yelp user data set, establishing friendship network figure, randomly selects wherein 90% friends company
For number of edges according to being training set, remaining 10% is used as test set；
S2: the nothing of having the right of two kinds of friendship networks based on topological characteristic is constructed respectively according to two kinds of network topology characteristics
Xiang Tu；
S3: the two class bipartite graphs of user and restaurant, user and taste are constructed respectively, are calculated according to above-mentioned two classes bipartite graph
Two kinds of behavioural characteristic similarity matrixs, then construct the non-directed graph of having the right of the friendship network based on user behavior characteristics；
S4: above-mentioned four kinds non-directed graphs of having the right are carried out respectively using corporations' detection algorithm (CNM algorithm) based on modularity
Community division.If any two user two o'clock is at least divided into together three times or above during above-mentioned four kinds of community divisions
One community, then it is assumed that the two users are friends.
In the step S1, it includes friend networks and have dinner place, taste information that Yelp data set, which provides, initially sets up friend
Friendly relational network figure, randomly select wherein 90% friends connect number of edges according to be training set, it is remaining be used as test set.
In the step S2, friends is established according to training set and haves no right non-directed graph G1=(V, E1), scheme G1Adjacency matrix
A=(aij)v×v, i, j ∈ { 1,2 ..., v }, in which:
According to adjacency matrix Av×v=(aij)v×v, i, j ∈ 1,2 ..., and v } following three kinds of network topology spies are found out respectively
Sign: resource allocation index (RA), Jaccard index (J) respectively obtain following each topological characteristic matrix:
RAv×v=(RAij)v×v,Jv×v=(Jij)v×v,i,j∈{1,2,...,v}.It the following is each eigenmatrix element expression
Formula:
Wherein Γ (i) be node i neighbor node set, k (z)=| Γ (z) | be node z degree.Each eigenmatrix
RAv×v, Jv×vLinear normalization is respectivelyEach element expression formula is as follows in above-mentioned matrix:
As above friends is had no right into non-directed graph G1Two kinds of non-directed graphs of having the right are separately converted to, wherein weight is respectively equal to
The value of eigenmatrix after above two normalization, i.e.,
In the step S3, by the record data of the existing behaviors such as place and taste of having dinner of Yelp user, build respectively
Vertical two class bipartite graphs, i.e. user-restaurant area, user-taste label.Process is as follows: it defines restaurant bipartite graph G=(X, E, R),
Wherein Xi={ x1,x2,...,xv, i ∈ { 1,2 ..., v } indicates v user, Ri={ r1,r2,...,rn},i∈{1,2,...,
N } indicate n restaurant, if user xi, i ∈ 1,2 ..., and v } removed restaurant rj,j∈{1,2,...,n}.Then with the Lian Bianbiao that has the right
Show that the user has removed the restaurant several times, weight dij, i ∈ { 1,2 ..., v }, j ∈ { 1,2 ..., n }, that is, the number gone.Together
Reason, can construct user-taste label bipartite graph G (X, E', T), wherein Xi={ x1,x2,...,xv, i ∈ 1,2 ..., and v } table
Show v user, Ti={ t1,t2,...,tm, i ∈ { 1,2 ..., m } indicates m taste label, if user xiSelect taste tj,j
∈{1,2,...,m}.Then indicate that the user has selected the taste several times, weight d with even side of having the righti'j,i∈{1,2,...,
V }, j ∈ { 1,2 ..., m }, the i.e. number of selection.
The step S3 the following steps are included:
S3-1: respectively according to user-restaurant and user-taste label bipartite graph, the section of any two user is calculated
Point similarity, for characterizing the behavioral difference between two users.Wherein dijIndicate user xiRemove restaurant rjNumber, then user
xiRemove restaurant rjProbability are as follows:
Wherein, k=1,2 ..., | v | indicate all users；
According to the definition of uncorrelated entropy, restaurant rjEntropy are as follows:
Wherein, EjIt is worth bigger, expression restaurant rjIt is more popular with users.
User xi,xjSelect the characteristic similarity (RSIM) in restaurant is defined as:
EigenmatrixEach element linear normalization result are as follows:
Similarly, in user-taste label bipartite graph, d 'ijIndicate user xiTasted taste tjNumber, then user xiIt tastes
Cross taste tjProbability are as follows:
According to the definition of uncorrelated entropy, taste tjEntropy are as follows:
Wherein, E 'ijIt is worth bigger, expression taste tjIt is more popular with users.
Then user selects similarity feature (TSIM of the restaurant on tasteij) is defined as:
EigenmatrixEach element linear normalization result are as follows:
S3-2: according to the friend networks that rebuild of above two user behavior characteristics, that is, have the right non-directed graph G2=(V,
E2), process is as follows: retaining user node, deletes all friends and connect side, whether has Lian Bian between two o'clock and even the weight on side takes
Certainly in user behavior characteristics similarity, the wherein company side E of friend networks2Weight be taken respectively from above-mentioned two eigenmatrix i.e.
In the step S4, using corporations' detection algorithm (CNM algorithm) based on weighting block degree respectively to above-mentioned four
A non-directed graph of having the right carries out community division, the following is the modularity Q of weighting Undirected networkswFormula are as follows:
Wherein, W is the weights sum on all sides in network, siIt is the intensity of node, i.e., all sides being connected with node i
Weight and wijIt is the weight on the company side between nodes i and node j, sisj/ (2W) is corresponding zero model interior joint i
The desired weight on the company side between node j, CiWith CjRespectively indicate node i and node j in a network belonging to corporations: such as
The two nodes of fruit belong to same corporations, then δ (Ci,Cj)=1；Otherwise value is 0.The step S4 the following steps are included:
S4-1: initialization: assume that each node is exactly an independent corporations when initial, i.e. v corporations, selection is based onNon-directed graph of having the right be object, the weights sum on all sides of the network is W1, module angle value Q=0, defines symmetrical square at this time
Battle array Fv×v, element f thereinijIndicate that the side right value in connection corporations and corporations accounts for the ratio of all side right values.Definition line adds
AlwaysIt indicates that the side right value of all nodes being connected in corporations accounts for the ratio of total weight value.Matrix F and auxiliary vectorElement be fijAnd ai, initial fij、aiIt calculates as follows:
ai=si/(2W1)
Wherein, fijNonzero value be according to be based on different characteristic i.e. topological characteristic, behavioural characteristic non-directed graph of having the right
Object and determine, the element of initial modularity Increment Matrix calculates as follows:
After obtaining initial module Increment Matrix, the most raft H being made of the greatest member of its every a line can be obtained；
S4-2: max { Δ Q is selected from most raft Hij, merge corresponding corporations GiAnd Gj, corporations' mark after label merging
Number be j；And update module degree Increment Matrix Δ Q, most raft H and auxiliary vector
S4-2-1: the update of Δ Q: deleting the element of the i-th row and the i-th column, updates the element of jth row and jth column, obtains
S4-2-2: the most update of raft H: after updating Δ Q, the greastest element of corresponding row and column in Yao Gengxin most raft
Element；
S4-2-3: auxiliary vectorUpdate it is as follows:
aj←ai+aj, then ai=0
And it records and merges later module angle value:
Q←Q+max{ΔQij}；
S4-2-4: step S4-2-2 is repeated until node all in network is all grouped into a corporations；
In the whole process of algorithm operation, only one maximum peak value of modularity Q.When in modularity Increment Matrix most
Big element is both less than after zero, and Q value just has dropped always.So as long as maximum element is by just in the modularity Increment Matrix
Become negative, so that it may stop merging, and think that result at this time is namely based onNon-directed graph network of having the right community structure
C1；
S4-3: selection is based onHave the right Undirected networks be object, repeat S4-1 process, can obtain
To being based onUndirected networks of having the right community structure C2,C3,C4；
S4-4: according to the network society for above based on four kinds of different characteristics including network topology characteristic and user behavior characteristics
Unity structure, i.e. C1,C2,C3,C4If any two user two o'clock during above-mentioned four kinds of community divisions at least three times or
Divided into the same community above, then it is assumed that the two users are friends.
Embodiment introduction for the present invention in user friend's relation excavation method of Yelp food and drink platform as described above, this hair
Bright is to combine the expansion of network topology characteristic and user behavior characteristics to traditional CNM algorithm, and final prediction result is higher, reaches
The requirement of actual use.It is merely illustrative and not restrictive for the invention.Those skilled in the art understand that In
Many changes, modifications, and even equivalents may be made in spirit and scope defined by invention claim, but falls within this
In the protection scope of invention.
Claims (1)
1. the friends method for digging of a kind of combination network topology characteristic and user behavior characteristics, it is characterised in that: the digging
Pick method the following steps are included:
S1: it includes friend networks and have dinner place, taste information that data set, which provides, initially sets up friendship network figure, at random
The friends for choosing wherein setting ratio connects number of edges according to being training set, and remainder is as test set；
S2: friends is established according to training set and haves no right non-directed graph G1=(V, E1), scheme G1Adjacency matrix Av×v=(aij)v×v,
I, j ∈ { 1,2 ..., v }, v indicate user's number, in which:
According to adjacency matrix Av×v=(aij)v×v, i, j ∈ 1,2 ..., and v } the following two kinds network topology characteristic is found out respectively: money
Source indicator of distribution RAv×v, Jaccard index Jv×v, respectively obtain following each topological characteristic matrix:
RAv×v=(RAij)v×v,Jv×v=(Jij)v×v, i, j ∈ { 1,2 ..., v } the following is each eigenmatrix element expression:
Wherein Γ (i) be node i neighbor node set, k (z)=| Γ (z) | be node z degree, each eigenmatrix RAv×v,
Jv×vLinear normalization is respectively
EigenmatrixEach element linear normalization result are as follows:
As above friends is had no right into non-directed graph G1Two kinds of non-directed graphs of having the right are separately converted to, wherein weight is respectively equal to above-mentioned
The value of eigenmatrix after two kinds of normalization, i.e.,
S3: by the record data in user existing have dinner place and taste behavior, two class bipartite graphs, i.e. user-are established respectively
Restaurant area, user-taste label, process are as follows: defining restaurant bipartite graph G=(X, E, R), wherein Xi={ x1,x2,...,
xv, i ∈ { 1,2 ..., v } indicates v user, Ri={ r1,r2,...,rn, i ∈ { 1,2 ..., n } indicates n restaurant, if with
Family xi, i ∈ 1,2 ..., and v } removed restaurant rj, j ∈ { 1,2 ..., n }, then with have the right even side indicate the user gone several times should
Restaurant, weight dij, i ∈ { 1,2 ..., v }, j ∈ { 1,2 ..., n }, that is, the number gone, similarly, building user-taste mark
It signs bipartite graph G (X, E', T), wherein Xi={ x1,x2,...,xv, i ∈ { 1,2 ..., v } indicates v user, Ti={ t1,
t2,...,tm, i ∈ { 1,2 ..., m } indicates m taste label, if user xiSelect taste tj, j ∈ { 1,2 ..., m }, then
With having the right, even side indicates that the user has selected the taste several times, weight d'ij, i ∈ { 1,2 ..., v }, j ∈ { 1,2 ..., m },
That is the number of selection；The S3 the following steps are included:
S3-1: respectively according to user-restaurant and user-taste label bipartite graph, the node phase of any two user is calculated
Like degree, for characterizing the behavioral difference between two users, wherein dijIndicate user xiRemove restaurant rjNumber, then user xiIt goes
Restaurant rjProbability are as follows:
Wherein, k=1,2 ..., | v |, indicate all users；
According to the definition of uncorrelated entropy, restaurant rjEntropy are as follows:
Wherein, EjIt is worth bigger, expression restaurant rjIt is more popular with users；
User xi,xjSelect the characteristic similarity RSIM in restaurant is defined as:
EigenmatrixEach element linear normalization result are as follows:
Similarly, in user-taste label bipartite graph, d'ijIndicate user xiTasted taste tjNumber, then user xiTasted mouth
Taste tjProbability are as follows:
According to the definition of uncorrelated entropy, taste tjEntropy are as follows:
Wherein, E 'jIt is worth bigger, expression taste tjIt is more popular with users；
Then user selects similarity feature (TSIM of the restaurant on tasteij) is defined as:
EigenmatrixEach element linear normalization result are as follows:
S3-2: rebuilding friend networks according to above two user behavior characteristics, that is, have the right non-directed graph G2=(V, E2), process
It is as follows: to retain user node, delete all friends and connect side, whether have Lian Bian between two o'clock and even the weight on side depends on user
Behavioural characteristic similarity, wherein the company side E of friend networks2Weight be taken respectively from above-mentioned two eigenmatrix i.e.
S4: carrying out community division to aforementioned four non-directed graph of having the right respectively using corporations' detection algorithm based on weighting block degree,
It the following is the modularity formula of weighting Undirected networks are as follows:
Wherein, W is the weights sum on all sides in network, siIt is the intensity of node, i.e., the weight on all sides being connected with node i
With wijIt is the weight on the company side between nodes i and node j, sisj/ (2W) is corresponding zero model interior joint i and section
The desired weight on the company side between point j, CiWith CjRespectively indicate node i and node j in a network belonging to corporations: if this
Two nodes belong to same corporations, then δ (Ci,Cj)=1；Otherwise value be 0, the S4 the following steps are included:
S4-1: initialization: assume that each node is exactly an independent corporations when initial, i.e. m corporations, selection is based on's
Non-directed graph have the right for object, the weights sum on all sides of the network is W1, module angle value Q=0, defines symmetrical matrix F at this timev×v,
Element f thereinijIndicate that the side right value in connection corporations and corporations accounts for the ratio of all side right values；The aggregation of definition lineIt indicates that the side right value of all nodes being connected in corporations accounts for the ratio of total weight value, matrix F and auxiliary vector
Element be fijAnd ai, initial fij、aiIt calculates as follows:
ai=si/(2W1)
Wherein, fijNonzero value be according to be based on different characteristic i.e. topological characteristic, behavioural characteristic non-directed graph object of having the right
It determines, each element of initial modularity Increment Matrix Δ Q calculates as follows:
After obtaining initial module Increment Matrix, the most raft H being made of the greatest member of its every a line can be obtained；
S4-2: max { Δ Q is selected from most raft Hij, merge corresponding corporations GiAnd Gj, corporations after label merging marked as
j；And update module degree Increment Matrix Δ Q, most raft H and auxiliary vector
S4-2-1: the update of Δ Q: deleting the element of the i-th row and the i-th column, updates the element of jth row and jth column, obtains
S4-2-2: the most update of raft H: after updating Δ Q, the greatest member of corresponding row and column in Yao Gengxin most raft；
S4-2-3: auxiliary vectorUpdate it is as follows:
aj←ai+aj, then ai=0
And it records and merges later module angle value:
Q←Q+max{ΔQij}
S4-2-4: step S4-2-2 is repeated until node all in network is all grouped into a corporations；
When element maximum in modularity Increment Matrix is from just becoming negative, just stopping merges, and thinks that result at this time is exactly base
InNon-directed graph network of having the right community structure C1；
S4-3: selection is based onHave the right Undirected networks be object, repeat S4-1 process, base can be obtained
InUndirected networks of having the right community structure C2,C3,C4；
S4-4: according to the network community knot for above based on four kinds of different characteristics including network topology characteristic and user behavior characteristics
Structure, i.e. C1,C2,C3,C4If any two user two o'clock during above-mentioned four kinds of community divisions at least three times or more
Divided into the same community, then it is assumed that the two users are friends.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201610907676.8A CN106570082B (en) | 2016-10-19 | 2016-10-19 | A kind of friends method for digging of combination network topology characteristic and user behavior characteristics |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201610907676.8A CN106570082B (en) | 2016-10-19 | 2016-10-19 | A kind of friends method for digging of combination network topology characteristic and user behavior characteristics |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN106570082A CN106570082A (en) | 2017-04-19 |
| CN106570082B true CN106570082B (en) | 2019-11-05 |
Family
ID=58533699
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201610907676.8A Active CN106570082B (en) | 2016-10-19 | 2016-10-19 | A kind of friends method for digging of combination network topology characteristic and user behavior characteristics |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN106570082B (en) |
Families Citing this family (13)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US10652096B2 (en) | 2017-02-22 | 2020-05-12 | University Of Notre Dame Du Lac | Methods and systems for inferring network structure from cascades |
| CN107357858B (en) * | 2017-06-30 | 2020-09-08 | 中山大学 | Network reconstruction method based on geographic position |
| CN109446171B (en) * | 2017-08-30 | 2022-03-15 | 腾讯科技（深圳）有限公司 | Data processing method and device |
| CN107909501B (en) * | 2017-12-05 | 2020-12-01 | 创新先进技术有限公司 | Smell and behavior association method, smell social method and device |
| CN108449311B (en) * | 2018-01-29 | 2020-08-04 | 浙江工业大学 | Social relationship hiding method based on attack node similarity |
| CN108491465B (en) * | 2018-03-06 | 2020-10-16 | 北京腾云天下科技有限公司 | Crowd diffusion method and computing device |
| CN110443265A (en) * | 2018-05-04 | 2019-11-12 | 北京京东尚科信息技术有限公司 | A kind of behavioral value method and apparatus based on corporations |
| CN108711064A (en) * | 2018-06-06 | 2018-10-26 | 中国农业银行股份有限公司 | A kind of method and device dividing customer relationship network |
| CN109377402B (en) * | 2018-09-14 | 2021-08-20 | 深圳大学 | Visualization method, device and equipment for social network data and storage medium |
| CN110929141B (en) * | 2018-09-20 | 2022-11-01 | 百度在线网络技术（北京）有限公司 | Group mining method, device, equipment and storage medium |
| CN110555172B (en) * | 2019-08-30 | 2023-04-07 | 京东科技控股股份有限公司 | User relationship mining method and device, electronic equipment and storage medium |
| CN110807052B (en) * | 2019-11-05 | 2022-08-02 | 佳都科技集团股份有限公司 | User group classification method, device, equipment and storage medium |
| CN112417312B (en) * | 2020-11-22 | 2023-02-10 | 同济大学 | Network social platform user classification method, storage medium and terminal |
Citations (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103325061A (en) * | 2012-11-02 | 2013-09-25 | 中国人民解放军国防科学技术大学 | Community discovery method and system |
| CN104021233A (en) * | 2014-06-30 | 2014-09-03 | 电子科技大学 | Social network friend recommendation method based on community discovery |
| CN104077279A (en) * | 2013-03-25 | 2014-10-01 | 中兴通讯股份有限公司 | Parallel community discovery method and device |
| CN104731962A (en) * | 2015-04-03 | 2015-06-24 | 重庆邮电大学 | Method and system for friend recommendation based on similar associations in social network |
| CN105574131A (en) * | 2015-12-14 | 2016-05-11 | 西安交通大学 | Social network friend making recommendation method and system based on dynamic community identification |
| CN106021325A (en) * | 2016-05-06 | 2016-10-12 | 腾讯科技（深圳）有限公司 | A friend recommendation method and device |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CA2964997A1 (en) * | 2013-10-25 | 2015-04-30 | Sysomos L.P. | Systems and methods for identifying influencers and their communities in a social data network |
-
2016
- 2016-10-19 CN CN201610907676.8A patent/CN106570082B/en active Active
Patent Citations (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103325061A (en) * | 2012-11-02 | 2013-09-25 | 中国人民解放军国防科学技术大学 | Community discovery method and system |
| CN104077279A (en) * | 2013-03-25 | 2014-10-01 | 中兴通讯股份有限公司 | Parallel community discovery method and device |
| CN104021233A (en) * | 2014-06-30 | 2014-09-03 | 电子科技大学 | Social network friend recommendation method based on community discovery |
| CN104731962A (en) * | 2015-04-03 | 2015-06-24 | 重庆邮电大学 | Method and system for friend recommendation based on similar associations in social network |
| CN105574131A (en) * | 2015-12-14 | 2016-05-11 | 西安交通大学 | Social network friend making recommendation method and system based on dynamic community identification |
| CN106021325A (en) * | 2016-05-06 | 2016-10-12 | 腾讯科技（深圳）有限公司 | A friend recommendation method and device |
Also Published As
| Publication number | Publication date |
|---|---|
| CN106570082A (en) | 2017-04-19 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN106570082B (en) | A kind of friends method for digging of combination network topology characteristic and user behavior characteristics | |
| Ibnoulouafi et al. | M-centrality: identifying key nodes based on global position and local degree variation | |
| Zarandi et al. | Community detection in complex networks using structural similarity | |
| Adamic et al. | How to search a social network | |
| CN107391542A (en) | A kind of open source software community expert recommendation method based on document knowledge collection of illustrative plates | |
| Jin et al. | Community detection in complex networks by density-based clustering | |
| CN107123056B (en) | Social big data information maximization method based on position | |
| De Souza et al. | Efficient network seeding under variable node cost and limited budget for social networks | |
| Chen et al. | A novel trust-based community detection algorithm used in social networks | |
| CN106789338B (en) | Method for discovering key people in dynamic large-scale social network | |
| Hasan et al. | Friend recommendation framework for social networking sites using user's online behavior | |
| CN107346333B (en) | Online social network friend recommendation method and system based on link prediction | |
| Zhang et al. | Influence maximization in messenger-based social networks | |
| Wu et al. | Coritivity-based influence maximization in social networks | |
| JP6470965B2 (en) | Advertisement selection device, advertisement selection method and program | |
| Jiang et al. | Discovery of really popular friends from social networks | |
| CN104657901A (en) | Community discovery method based on label propagation in random walk | |
| CN106530100A (en) | Community discovery technical method facing confidence-level social network | |
| Nia et al. | Leveraging social interactions to suggest friends | |
| CN112035545B (en) | Competition influence maximization method considering non-active node and community boundary | |
| CN111177529A (en) | Network influence maximization method based on node attribute sparsity | |
| CN106021441B (en) | A kind of mechanism friend recommendation method and system | |
| Zhu et al. | Detecting network communities via greedy expanding based on local superiority index | |
| CN108595684A (en) | A kind of overlapping community discovery method and system based on preferential learning mechanism | |
| Hosseini et al. | A method based on link prediction for identifying set of super-spreaders in complex networks |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |