技术领域technical field
本发明属于社会网络及计算机应用技术领域，尤其涉及一种基于关系组合优化和种子扩张的多关系社区发现方法。The invention belongs to the technical field of social network and computer application, and in particular relates to a multi-relationship community discovery method based on relation combination optimization and seed expansion.
背景技术Background technique
社会网络(Social Network)是由许多节点和连边构成的网状结构，节点可以对应现实生活中的人以及各种社会组织机构，节点之间的连边可以对应日常生活中的各种交往关系，比如人与人之间的朋友、家人、同学等社会关系，也可以是微信、电话、邮件等联络关系。社区发现是包括社会网络在内的复杂网络的一个重要研究方向，在电子商务、公共安全、生物学等领域都有着巨大的应用价值。社区是指网络中一些相互之间拥有较多共同特征，联系比较多的节点聚类。网络拓补结构具体表现为同一社区的节点之间联系比较紧密，而不属于同一社区的节点之间联系比较稀疏。社区发现是社会网络分析的一个基本任务，是对网络中存在的社区结构进行挖掘，研究网络的社区对理解整个网络的结构和功能具有至关重要的作用。一般对社会网络的研究分析大都是对网络中的一种关系进行研究，而现实生活中的社会网络个体之间都存在多种类型的关系，比如人与人之间存在着朋友、同学、家人等社会关系。而Web2.0时代的到来更使人们之间存在的交流联系方式变得多种多样，除了传统的电话和短信，还有微信、微博、人人Facebook、Twitter、Youtube等多种基于互联网的交流联系也在社会网络中普遍存在，甚至在同一种交流工具中也存在着多种交流方式，比如微博中人们之间可以通过评论、转发、点赞等多种渠道来产生交流。多关系的社会网络普遍存在于现实生活中。目前对社会网络的社区发现方法基本都是基于一种关系的研究，而由于社会个体之间的交流方式存在一定主观性，只采用一种关系不能充分掌握个体间的交流信息，很可能会因为信息不全面导致社区划分结果最终跟现实不对应。同时某种交流方式可能会因为更容易跟陌生人或平常不熟悉的人发生联系而产生较多社交噪音，这些噪音也会掩盖现实生活中真正的社区结构。现有的一部分多关系社区发现方法在对多关系网络进行社区发现时，将各种关系组成的网络都一视同仁，但实际多关系社会网络中，由于交流方式的不同，每一种关系的社交噪音是不一样的。这样的方法虽然可以使各关系之间的社区信息互相补充，但同时也会引入各社交关系的噪音，在有些社交关系噪音比较大的情况下有可能会造成综合考虑多种关系进行社区发现的结果反而不如只考虑单个关系进行社区发现的结果。A social network is a network structure composed of many nodes and edges. Nodes can correspond to people in real life and various social organizations. The edges between nodes can correspond to various communication relationships in daily life. , such as social relationships such as friends, family members, and classmates between people, or contact relationships such as WeChat, telephone, and email. Community detection is an important research direction of complex networks including social networks, and has great application value in e-commerce, public security, biology and other fields. Community refers to the clustering of some nodes in the network that have more common features and more connections. The network topology structure specifically shows that the nodes in the same community are closely connected, while the nodes that do not belong to the same community are relatively sparsely connected. Community discovery is a basic task of social network analysis. It is to mine the community structure existing in the network. The study of community in the network plays a vital role in understanding the structure and function of the entire network. Generally, most of the research and analysis of social networks is to study a relationship in the network, and there are many types of relationships between individuals in social networks in real life, such as friends, classmates, and family members among people. and other social relations. The advent of the Web 2.0 era has made the communication and contact methods between people more diverse. In addition to traditional phone calls and text messages, there are also various Internet-based communication methods such as WeChat, Weibo, Renren Facebook, Twitter, and Youtube. Communication connections are also common in social networks, and there are even multiple communication methods in the same communication tool. For example, in Weibo, people can communicate through multiple channels such as comments, reposts, and likes. Multi-relational social networks are ubiquitous in real life. At present, the community discovery methods of social networks are basically based on the research of a relationship, and due to the subjectivity of the communication methods between social individuals, only one relationship cannot fully grasp the communication information between individuals, which may be due to Incomplete information leads to community division results that ultimately do not correspond to reality. At the same time, a certain communication method may generate more social noise because it is easier to connect with strangers or unfamiliar people, and these noises will also cover up the real community structure in real life. Some of the existing multi-relationship community discovery methods treat the networks composed of various relationships equally when performing community discovery on multi-relationship networks. However, in actual multi-relationship social networks, due to different communication methods, the social noise of each relationship are different. Although such a method can make the community information between the relationships complement each other, it will also introduce the noise of each social relationship. In some cases where the noise of some social relationships is relatively large, it may cause the comprehensive consideration of multiple relationships for community discovery. The results are rather inferior to those for community discovery considering only a single relation.
综上所述，现有技术存在的问题是：目前对社会网络的社区发现方法时忽略了各关系的差异性，将各个关系所带来的信息一视同仁，因此存在综合各关系网络的社区信息时也引入了各关系网络所携带的社交噪音，造成社区发现准确率不够高，某些关系噪音较大时甚至会造成综合考虑多种关系进行社区发现的结果反而不如只考虑单个关系进行社区发现的结果。To sum up, the problems existing in the existing technology are: the current community discovery method for social networks ignores the differences of each relationship and treats the information brought by each relationship equally. It also introduces the social noise carried by each relationship network, resulting in the accuracy of community discovery is not high enough. When some relationship noises are large, the result of community discovery that considers multiple relationships is not as good as community discovery that only considers a single relationship. result.
发明内容Contents of the invention
针对现有技术存在的问题，本发明提供了一种基于关系组合优化和种子扩张的多关系社区发现方法。Aiming at the problems existing in the prior art, the present invention provides a multi-relational community discovery method based on relational combination optimization and seed expansion.
本发明是这样实现的，一种基于关系组合优化和种子扩张的多关系社区发现方法，所述基于关系组合优化和种子扩张的多关系社区发现方法通过多目标优化优化网络中各种关系的权重配比将多关系网络融合成一个能有效综合各关系社区信息的同时噪音低的单关系网络，然后综合多关系网络中各关系的社区划分信息将在各个关系中都处于同一个社区的人群寻找出来，以这些人群组成的小社区作为种子社区，采用种子扩张策略对多关系社会网络进行社区挖掘，得到准确率更高的的社区结构划分；The present invention is achieved in this way, a multi-relationship community discovery method based on relationship combination optimization and seed expansion, the multi-relationship community discovery method based on relationship combination optimization and seed expansion optimizes the weights of various relationships in the network through multi-objective optimization Matching integrates multi-relational networks into a single-relational network that can effectively synthesize the information of each relational community and has low noise, and then integrates the community division information of each relation in the multi-relational network to search for people who are in the same community in each relation Come out, take the small community composed of these people as the seed community, and use the seed expansion strategy to mine the multi-relationship social network to obtain a more accurate community structure division;
所述权重配比优化子目标一采用模块度作为衡量结果社区结构强度和可靠性的指标，计算结果Ca的模块度Qa，模块度计算如下：The weight ratio optimization sub-goal one uses modularity as an index to measure the strength and reliability of the community structure of the result, and calculates the modularity Qa of the result Ca . The modularity is calculated as follows:
其中Ai，j是整个网络的邻接矩阵，m是网络中包含的边的数目，ki和kj分别表示节点i和节点j的度数，δ(Ci，Cj)的取值取决于i和j是否处于同一个社区内，是的话δ(Ci，Cj)取值为，否则话其取值为0；Among them, Ai, j is the adjacency matrix of the entire network, m is the number of edges contained in the network, ki and kj represent the degrees of node i and nodej respectively, and the value of δ(Ci , Cj ) depends on Whether i and j are in the same community, if yes, the value of δ(Ci , Cj ) is 0; otherwise, it is 0;
所述权重配比优化子目标二采用NMI作为社区结构信息相似性衡量标准，按如下计算：The weight ratio optimization sub-goal 2 uses NMI as the similarity measure of community structure information, which is calculated as follows:
其中混淆矩阵H的行代表真实的社区划分结果，H的列代表划分算法画出来的社区结果。CA和CB分别代表A，B两个结果包含的社区个数，Hij代表应该在社区i中却出现在社区j中的节点个数，Hi.和H.j分别代表第i行和第j列的社区的节点数之和，N是整个网络中所含的节点数目；当NMI＝1时，代表A和B两个结果的社区结构完全相同，NMI＝0，时代表完全不一样；The rows of the confusion matrix H represent the real community division results, and the columns of H represent the community results drawn by the division algorithm. CA and CB respectively represent the number of communities contained in the two results of A and B, Hij represents the number of nodes that should be in community i but appear in community j, Hi. and H.j represent row i respectively and the sum of the number of nodes in the community in column j, N is the number of nodes contained in the entire network; when NMI=1, it means that the community structures of the two results of A and B are exactly the same; when NMI=0, it means that they are completely different. Same;
所述种子扩张策略选取节点数最多的社区Si作为种子社区；计算种子社区Si与其余候选种子社区以及剩余节点的相似度,计算式子如下：The seed expansion strategy selects the community Si with the largest number of nodes as the seed community; calculates the similarity between the seed community Si and other candidate seed communities and the remaining nodes, and the calculation formula is as follows:
u和v分别是社区Si，Sj中的节点，ni和nj分别是两个社区中节点的数量，和是节点编号集合。u and v are the nodes in communities Si and Sj respectively, ni and nj are the numbers of nodes in the two communities respectively, with is a set of node numbers.
进一步，所述基于关系组合优化和种子扩张的多关系社区发现方法包括以下步骤：Further, the multi-relational community discovery method based on relational combination optimization and seed expansion includes the following steps:
1)将多关系网络的各关系直接按照相同比例来配置权重把多关系网络合并成一个带权的单关系网络A；1) The weights of each relationship in the multi-relationship network are directly configured according to the same ratio, and the multi-relationship network is merged into a weighted single-relationship network A;
2)采用一种单关系的社区划分方法对网络A进行社区划分，所得的社区划分结果记为Ca，接着采用一种衡量社区发现结果可靠性及结构强度的指标对结果Ca进行衡量，衡量出的值记为Qa；2) Use a single-relational community division method to divide the community of network A, and record the result of community division as Ca , then use an index to measure the reliability and structural strength of the community discovery results to measure the result Ca , The measured value is recorded as Qa ;
3)以各关系的权重配比作为决策变量，采用一种多目标优化方法同时对下列两个子目标进行优化来获得一组最优决策变量集；3) Take the weight ratio of each relationship as the decision variable, and use a multi-objective optimization method to optimize the following two sub-objectives at the same time to obtain a set of optimal decision variable sets;
优化子目标一：新的权重配比合并成的单关系网络B与网络A的社区划分结果的结构衡量指标差值尽可能大；Optimization sub-goal 1: The difference between the structural indicators of the community division results of the single-relationship network B and network A combined by the new weight ratio is as large as possible;
优化子目标二：新的权重配比合并成的单关系网络B与网络A的社区划分结果所显示的社区结构信息相似性尽可能大。Optimization sub-goal 2: The similarity of the community structure information shown by the community division results of the single-relationship network B and network A combined by the new weight ratio is as large as possible.
4)在步骤3)获得的最优决策变量集中选择使子目标一最大的权重配比将多关系网络融合成单关系网络M，并采用一种单关系社区发现方法对M进行社区发现，将所获社区个数记为K；4) In the optimal decision variable set obtained in step 3), select the weight ratio that maximizes sub-goal 1 to fuse the multi-relational network into a single-relational network M, and use a single-relational community discovery method to discover the community of M. The number of communities obtained is recorded as K;
5)采用一种单关系社区发现方法分别对每个关系组成的网络进行社区划分；5) A single-relationship community discovery method is used to divide the network composed of each relation into communities;
6)设置迭代标志L＝0，对步骤5)各关系社区发现的结果进行统计，将在所有关系中都处于一个社区的节点作为种子社区放入种子社区集合CL中；6) Set iteration sign L=0, step 5) make statistics on the results found in each relational community, put the nodes in one community in all relations into the seed community set CL as the seed community;
7)通过单关系网络M通过一种相似度计算方法来计算网络中各节点之间的相似度；7) Calculate the similarity between each node in the network through a similarity calculation method through the single-relationship network M;
8)若L＝0，令L＝L+1，集合CL＝CL-1，进行下一步；若L>0,检测集合CL与CL-1是否一样，是则转步骤11)，否则令L＝L+1，集合CL＝CL-1进行下一步；8) If L=0, set L=L+1, set CL =CL-1 , proceed to the next step; if L>0, check whether the sets CL and CL-1 are the same, if yes, go to step 11) , otherwise let L=L+1, set CL =CL-1 to proceed to the next step;
9)将种子社区候选集合CL中的尚未参与过合并的社区按照社区包含的节点数量从大到小进行排序，选取排序最高的社区Si作为种子社区；9) Sort the communities that have not yet participated in the merger in the seed community candidate set CL according to the number of nodes contained in the community from large to small, and select the community Si with the highest ranking as the seed community;
10)通过步骤7)计算出来的相似度计算种子社区Si与其余候选种子社区以及剩余节点的相似度记为Sim；10) Calculate the similarity between the seed community Si and other candidate seed communities and the remaining nodes through the similarity calculated in step 7) and record it as Sim;
11)选取与Si相似度超过设定阈值β的社区和节点放入候选区，通过一种局部适应度计算方法计算Si当前适应度F以及候选区各社区的当前适应度Fh，然后分别计算候选合并区的社区和节点与Si合并后的适应度值记为Fnew,接着计算Fnew相对于Si原来的适应度F的增长率Vs以及候选社区适应度Fnew的增长率Vh；11) Select communities and nodes whose similarity with Si exceeds the set threshold β and put them into the candidate area, calculate the current fitness F of Si and the current fitness Fh of each community in the candidate area through a local fitness calculation method, and then Calculate the fitness value of the merged communities and nodes in the candidate merged area and Si respectively, and record it as Fnew , and then calculate the growth rate Vs of Fnew relative to the original fitness F of Si and the growth of candidate community fitness Fnew Rate Vh ;
12)在Vs和Vh都大于增长率阈值δ的前提下，选使Vs+Vh最大的候选社区Sj与Si合并成一个新社区，更新Si和种子社区集合CL，返回步骤10)；若没有符合条件的，则检查集合CL中现有社区是否都已是合并过的，否的话返回步骤9)，是的话将集合CL中所有社区的合并记录清零，返回步骤8)；12) On the premise that both Vs and Vh are greater than the growth rate threshold δ, select the candidate community Sj and Si with the largest Vs + Vh to merge into a new community, update Si and the seed community set CL , Return to step 10); if there is no eligible community, check whether the existing communities in the set CL have been merged, if not, return to step 9), if yes, clear the merged records of all communities in the set CL , return to step 8);
13)检查网络中社区数目，若小于等与K，则输出结果，程序结束，输出集合CL；若大于K，则执行如下消除策略；以包含节点数目最多的前K个社区为目标，依次计算剩余社区及节点与他们的相似度，将剩余社区和节点归并入跟他们相似度最高的前K个社区，更新集合CL，最后输出社区集合CL作为最终划分结果。13) Check the number of communities in the network, if it is less than or equal to K, then output the result, the program ends, and output the set CL ; if it is greater than K, execute the following elimination strategy; aim at the top K communities with the largest number of nodes, and sequentially Calculate the similarity between the remaining communities and nodes and them, merge the remaining communities and nodes into the top K communities with the highest similarity with them, update the setCL , and finally output the community setCL as the final division result.
进一步，采用单关系社区发现算法BGLL分别对四个关系组成的网络进行社区划分，统计划分结果根据式子得到亲密度矩阵I，其中Iij为节点i,j在矩阵中对应的值，N为维度的总数这里是4,m表示第几个维度，Cm(i，j)表示两点在m维度是否被划分在同一社区，若两点在第m个维度被划为同一社区则Cm(i，j)值1，否则的话为0；遍历矩阵I，将所有值小于4的数全部设置为零，得到区域矩阵F；对矩阵F进行深度优先遍历，得到其所有的连通子区域，将子区域节点数目超过1的区域存入候选种子社区集合CL，L＝0。Further, the single-relationship community discovery algorithm BGLL is used to divide the community of the network composed of four relations, and the statistical division results are according to the formula Get the intimacy matrix I, where Iij is the corresponding value of node i and j in the matrix, N is the total number of dimensions here is 4, m represents the dimension, Cm (i, j) represents two points in the m dimension Whether they are divided into the same community, if the two points are divided into the same community in the m-th dimension, the value of Cm (i, j) is 1, otherwise it is 0; traverse the matrix I, and set all the values less than 4 to Zero, get the area matrix F; perform depth-first traversal on the matrix F to get all its connected sub-areas, and store the areas with more than 1 sub-area nodes into the candidate seed community set CL , L=0.
进一步，通过单关系网络M来计算网络中各节点之间的相似度Sim:Further, calculate the similarity Sim between each node in the network through the single relational network M:
其中K表示i,j被划为相同社区的维度个数，N＝4，Δ增益因子为1，W(i，j)时节点i和节点j的连接边权重，com(i，j)两个节点邻居节点交集，N(i，j)是两个节点的邻居节点并集。Among them, K represents the number of dimensions that i and j are divided into the same community, N=4, Δ gain factor is 1, when W(i, j) is the connection edge weight of node i and node j, com(i, j) two N(i, j) is the union of neighbor nodes of two nodes.
进一步，选取与Si相似度超过设定阈值γ＝1的社区和节点放入候选区，计算Si当前适应度F以及候选区各社区的当前适应度Fh，计算公式如下：Further, select communities and nodes whose similarity with Si exceeds the set threshold γ=1 and put them into the candidate area, calculate the current fitness F of Si and the current fitness Fh of each community in the candidate area, the calculation formula is as follows:
其中式子的是社区内部边的权重之和的两倍，是与社区外部边的权重之和，α为调控社区规模大小的参数，取值设为一；where the formula is twice the sum of the weights of the edges within the community, is the sum of the weights of the external edges of the community, α is a parameter to regulate the size of the community, and the value is set to one;
然后分别计算候选合并区的社区和节点与Si合并后的适应度值记为，然后计算Fnew相对于Si原来的适应度F的增长率Vs以及候选社区适应度Fh的增长率Vh；Then calculate the fitness value of the community and node in the candidate merged area after merging with Si , and then calculate the growth rate Vs of Fnew relative to the original fitness F of Si and the growth rate of the candidate community fitness Fh Vh ;
在Vs和Vh都大于增长率阈值δ＝0.1的前提下，选取Vs+Vh最大的那个社区与Si合并成一个新社区，更新Si和种子社区集合CL；若没有符合条件的，则检查集合CL中现有社区是否都已是合并过的；是的话将集合CL中所有社区的合并记录清零；On the premise that both Vs and Vh are greater than the growth rate threshold δ=0.1, select the community with the largest Vs +Vh and merge it with Si to form a new community, and update Si and the seed community set CL ; condition, check whether the existing communities in the set CL have been merged; if yes, clear the merge records of all communities in the set CL ;
检查社区数目，若小于等与K，则输出结果，程序结束，输出集合CL；若大于K，则以包含节点数目最多的前K个社区为目标，依次计算剩余社区与他们的相似度，将剩余社区和节点归并入跟他们相似度最高的前K个社区，更新集合CL，最后输出社区集合CL作为最终划分结果。Check the number of communities, if it is less than or equal to K, output the result, end the program, and output the set CL ; if it is greater than K, take the top K communities containing the largest number of nodes as the target, and calculate the similarity between the remaining communities and them in turn, Merge the remaining communities and nodes into the top K communities with the highest similarity with them, update the setCL , and finally output the community setCL as the final division result.
本发明的另一目的在于提供一种应用所述基于关系组合优化和种子扩张的多关系社区发现方法的社会网络。Another object of the present invention is to provide a social network using the multi-relational community discovery method based on relational combination optimization and seed expansion.
本发明的另一目的在于提供一种应用所述基于关系组合优化和种子扩张的多关系社区发现方法的计算机。Another object of the present invention is to provide a computer for applying the multi-relational community discovery method based on relational combination optimization and seed expansion.
本发明的优点及积极效果为：Advantage of the present invention and positive effect are:
1.本发明对多关系网络中的各种关系通过权重配比来进行组合优化，能够在综合各关系网络有效信息的同时更好地克服不同关系网络带来的社交噪音，在各关系噪音较大时，依然能够获得比较准确的社区划分结果。本发明通过综合多关系网络中各关系的社区划分信息将在各个关系中都处于同一个社区的人群寻找出来，这些非常固定的社交圈子一般都处于所在社区的核心位置，以他们作为种子社区进行扩张更有利于发现出多关系网络中隐含的真实社区。人工网络实验表明，本发明的社区发现结果有的准确性比传统方法平均提高了越9％，具体效果见图4。在各关系携带的噪音比例差距高达50％的恶劣情况下，传统多关系方法受噪音影响社区发现结果准确性降低到71％已不如单独采用噪音最小的关系的82％，而这种情况下本发明的准确性为86.3％，具体效果见图5。1. The present invention combines and optimizes the various relationships in the multi-relationship network through the weight ratio, which can better overcome the social noise brought by different relationship networks while synthesizing the effective information of each relationship network. When it is large, a relatively accurate community division result can still be obtained. The present invention finds the people who are in the same community in each relationship by synthesizing the community division information of each relationship in the multi-relationship network. These very fixed social circles are generally at the core of the community where they are located, and they are used as seed communities. Expansion is more conducive to discovering the hidden real communities in multi-relational networks. The artificial network experiment shows that the accuracy of the community discovery results of the present invention is 9% higher than that of the traditional method on average, and the specific effect is shown in FIG. 4 . In the harsh situation where the proportion of noise carried by each relationship is as high as 50%, the traditional multi-relationship method is affected by the noise. The accuracy of the community discovery results is reduced to 71%, which is not as good as the 82% of the relationship with the least noise alone. The accuracy of the invention is 86.3%, and the specific effect is shown in Figure 5.
附图说明Description of drawings
图1是本发明实施例提供的基于关系组合优化和种子扩张的多关系社区发现方法流程图。Fig. 1 is a flowchart of a multi-relational community discovery method based on relational combination optimization and seed expansion provided by an embodiment of the present invention.
图2是本发明实施例提供的基于关系组合优化和种子扩张的多关系社区发现实现流程图。Fig. 2 is a flow chart for realizing multi-relational community discovery based on relational combination optimization and seed expansion provided by an embodiment of the present invention.
图3是本发明实施例提供的的结果与只采用一种关系进行社区发现的结果对比示意图。Fig. 3 is a schematic diagram of the comparison between the results provided by the embodiment of the present invention and the results of community discovery using only one relationship.
图4是本发明实施例提供的与传统多关系社区发现方法PMM在不同噪音下的结果对比示意图。Fig. 4 is a schematic diagram of the comparison between the results provided by the embodiment of the present invention and the traditional multi-relational community discovery method PMM under different noises.
图5是本发明实施例提供的本发明具体效果示意图。Fig. 5 is a schematic diagram of the specific effect of the present invention provided by the embodiment of the present invention.
具体实施方式detailed description
为了使本发明的目的、技术方案及优点更加清楚明白，以下结合实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。In order to make the object, technical solution and advantages of the present invention more clear, the present invention will be further described in detail below in conjunction with the examples. It should be understood that the specific embodiments described here are only used to explain the present invention, not to limit the present invention.
下面结合附图对本发明的应用原理作详细的描述。The application principle of the present invention will be described in detail below in conjunction with the accompanying drawings.
本发明实施例提供的基于关系组合优化和种子扩张的多关系社区发现方法通过优化网络中各种关系的权重配比将多关系网络融合成一个能有效综合各关系社区信息的同时噪音低的单关系网络，然后综合多关系网络中各关系的社区划分信息将在各个关系中都处于同一个社区的人群寻找出来，以这些人群组成的小社区作为种子社区，采用一种种子扩张策略对多关系社会网络进行社区挖掘，从而得到准确率更高的的社区结构划分。The multi-relationship community discovery method based on relation combination optimization and seed expansion provided by the embodiment of the present invention fuses multi-relationship networks into a single unit with low noise and can effectively synthesize the information of each relational community by optimizing the weight ratio of various relations in the network. relationship network, and then integrate the community division information of each relationship in the multi-relationship network to find out the people who are in the same community in each relationship, and use the small community composed of these people as the seed community, and adopt a seed expansion strategy to multi-relationship The social network performs community mining to obtain a more accurate community structure division.
如图1所示，本发明实施例提供的基于关系组合优化和种子扩张的多关系社区发现方法包括以下步骤：As shown in Figure 1, the multi-relational community discovery method based on relational combination optimization and seed expansion provided by the embodiment of the present invention includes the following steps:
S101：将多关系网络的各关系直接按照1:1比例来配置权重将多关系网络合并成一个带权重的单关系网络；S101: directly configure the weights of each relationship in the multi-relationship network according to a ratio of 1:1, and merge the multi-relationship network into a weighted single-relationship network;
S102：采用一种单关系社区划分算法对该网络进行社区划分，采用某种衡量指标计算划分结果社区结构强度；S102: Use a single-relationship community division algorithm to divide the network into communities, and use a certain measurement index to calculate the community structure strength of the division result;
S103：采用一种多目标进化算法对各维度关系的权重组合配比进行优化优化目标一为的新权重合并成的网络的社区划分结果与最开始1:1合并成的网络社区划分结果的社区结构强度指标之差尽可能大；优化目标二采用一种指标衡量二者社区划分结果相似度，使相似度尽可能高；S103: Use a multi-objective evolutionary algorithm to optimize the weight combination ratio of each dimension relationship. The optimization goal is the community division result of the network combined with the new weight and the community division result of the network community formed by the initial 1:1 merger. The difference between the structural strength indicators is as large as possible; the second optimization goal is to use an indicator to measure the similarity of the two community division results, so that the similarity is as high as possible;
S104：用优化后的权重配比将多关系网络转化成单关系网络；S104: Transform the multi-relationship network into a single-relationship network by using the optimized weight ratio;
S105：采用一种单关系社区发现算法分别对每个关系组成的网络进行社区划分，统计关系社区发现的结果，将在所有关系中都处于一个社区的节点作为候选种子社区；S105: Use a single-relationship community discovery algorithm to divide the network composed of each relationship into communities, count the results of relationship community discovery, and use nodes that are in one community in all relationships as candidate seed communities;
S106：通过所选用的社区相似度函数和局部适应度函数在种子社区和剩余节点间进行合并；S106: Merge between the seed community and the remaining nodes through the selected community similarity function and local fitness function;
S107：合并结束后检测社区数目决定是否使用消除策略，输出最终社区划分结果。S107: Detect the number of communities after the merging to determine whether to use the elimination strategy, and output the final community division result.
本发明实施例提供的基于关系组合优化和种子扩张的多关系社区发现方法具体包括以下步骤：The multi-relational community discovery method based on relational combination optimization and seed expansion provided by the embodiment of the present invention specifically includes the following steps:
1)将多关系网络的各关系直接按照相同比例来配置权重把多关系网络合并成一个带权的单关系网络A。1) The weights of each relationship in the multi-relationship network are directly configured according to the same ratio, and the multi-relationship network is merged into a weighted single-relationship network A.
2)采用一种单关系的社区划分方法对网络A进行社区划分，所得的社区划分结果记为Ca，接着采用一种衡量社区发现结果可靠性及结构强度的指标对结果Ca进行衡量，衡量出的值记为Qa。2) Use a single-relational community division method to divide the community of network A, and record the result of community division as Ca , then use an index to measure the reliability and structural strength of the community discovery results to measure the result Ca , The measured value is denoted as Qa .
3)以各关系的权重配比作为决策变量，采用一种多目标优化方法同时对下列两个子目标进行优化来获得一组最优决策变量集；3) Take the weight ratio of each relationship as the decision variable, and use a multi-objective optimization method to optimize the following two sub-objectives at the same time to obtain a set of optimal decision variable sets;
优化子目标一：新的权重配比合并成的单关系网络B与网络A的社区划分结果的结构衡量指标差值尽可能大；Optimization sub-goal 1: The difference between the structural indicators of the community division results of the single-relationship network B and network A combined by the new weight ratio is as large as possible;
优化子目标二：新的权重配比合并成的单关系网络B与网络A的社区划分结果所显示的社区结构信息相似性尽可能大，二者社区结构信息相似性可以用一些常用的指标，比如标准化互信息NMI。Optimization sub-goal 2: The community structure information similarity shown by the community division results of the single-relationship network B and network A combined by the new weight ratio is as large as possible. The similarity of the community structure information between the two can use some commonly used indicators. For example, standardized mutual information NMI.
4)在步骤3)获得的最优决策变量集中选择使子目标一最大的权重配比将多关系网络融合成单关系网络M，并采用一种单关系社区发现方法对M进行社区发现，将所获社区个数记为K。4) In the optimal decision variable set obtained in step 3), select the weight ratio that maximizes the sub-objective one to fuse the multi-relationship network into a single-relationship network M, and use a single-relationship community discovery method to discover the community of M. The number of communities obtained is recorded as K.
5)采用一种单关系社区发现方法分别对每个关系组成的网络进行社区划分。5) A single-relation community discovery method is used to divide the community of the network composed of each relation.
6)设置迭代标志L＝0，对步骤5)各关系社区发现的结果进行统计，将在所有关系中都处于一个社区的节点作为种子社区放入种子社区集合CL中。6) Set the iteration flag L=0, make statistics on the results found in each relational community in step 5), and put the nodes in one community in all relations into the seed community setCL as the seed community.
7)通过单关系网络M通过一种相似度计算方法来计算网络中各节点之间的相似度。7) Calculate the similarity between each node in the network through a similarity calculation method through the single-relationship network M.
8)若L＝0，令L＝L+1，集合CL＝CL-1，进行下一步；若L>0,检测集合CL与CL-1是否一样，是则转步骤11)，否则令L＝L+1，集合CL＝CL-1进行下一步。8) If L=0, set L=L+1, set CL =CL-1 , proceed to the next step; if L>0, check whether the sets CL and CL-1 are the same, if yes, go to step 11) , otherwise let L=L+1, and set CL =CL-1 to proceed to the next step.
9)将种子社区候选集合CL中的尚未参与过合并的社区按照社区包含的节点数量从大到小进行排序，选取排序最高的社区Si作为种子社区。9) Sort the communities in the seed community candidate set CL that have not yet participated in the merger according to the number of nodes contained in the community from large to small, and select the community Si with the highest ranking as the seed community.
10)通过步骤7)计算出来的相似度计算种子社区Si与其余候选种子社区以及剩余节点的相似度记为Sim。10) Through the similarity calculation calculated in step 7), the similarity between the seed community Si and other candidate seed communities and remaining nodes is denoted as Sim.
11)选取与Si相似度超过设定阈值β的社区和节点放入候选区，通过一种局部适应度计算方法计算Si当前适应度F以及候选区各社区的当前适应度Fh，然后分别计算候选合并区的社区和节点与Si合并后的适应度值记为Fnew,接着计算Fnew相对于Si原来的适应度F的增长率Vs以及候选社区适应度Fnew的增长率Vh。11) Select communities and nodes whose similarity with Si exceeds the set threshold β and put them into the candidate area, calculate the current fitness F of Si and the current fitness Fh of each community in the candidate area through a local fitness calculation method, and then Calculate the fitness value of the merged communities and nodes in the candidate merged area and Si respectively, and record it as Fnew , and then calculate the growth rate Vs of Fnew relative to the original fitness F of Si and the growth of candidate community fitness Fnew Rate Vh .
12)在Vs和Vh都大于增长率阈值δ的前提下，选使Vs+Vh最大的候选社区Sj与Si合并成一个新社区，更新Si和种子社区集合CL，返回步骤10)；若没有符合条件的，则检查集合CL中现有社区是否都已是合并过的，否的话返回步骤9)，是的话将集合CL中所有社区的合并记录清零，返回步骤8)。12) On the premise that both Vs and Vh are greater than the growth rate threshold δ, select the candidate community Sj and Si with the largest Vs + Vh to merge into a new community, update Si and the seed community set CL , Return to step 10); if there is no eligible community, check whether the existing communities in the set CL have been merged, if not, return to step 9), if yes, clear the merged records of all communities in the set CL , Go back to step 8).
13)检查网络中社区数目，若小于等与K，则输出结果，程序结束，输出集合CL；若大于K，则执行如下消除策略；13) Check the number of communities in the network, if it is less than or equal to K, output the result, the program ends, and output the setCL ; if it is greater than K, execute the following elimination strategy;
以包含节点数目最多的前K个社区为目标，依次计算剩余社区及节点与他们的相似度，将剩余社区和节点归并入跟他们相似度最高的前K个社区，更新集合CL，最后输出社区集合CL作为最终划分结果。Taking the top K communities with the largest number of nodes as the target, calculate the similarity between the remaining communities and nodes and them in turn, merge the remaining communities and nodes into the top K communities with the highest similarity with them, update the set CL , and finally output The community set CL is used as the final division result.
下面结合附图对本发明的应用原理作进一步的描述。The application principle of the present invention will be further described below in conjunction with the accompanying drawings.
本发明实施例提供的基于关系组合优化和种子扩张的多关系社区发现方法包括以下步骤：The multi-relational community discovery method based on relational combination optimization and seed expansion provided by the embodiment of the present invention includes the following steps:
步骤一：输入多关系网络，并将各关系网络处理成邻接矩阵，输入相似度阈值σ＝1及增长率阈值β＝0.1；Step 1: Input multi-relational networks, and process each relational network into an adjacency matrix, input similarity threshold σ=1 and growth rate threshold β=0.1;
采用的多关系网络为人工生成网络，人造网络的大小为350个节点，包含三个社区，每个社区分别包括50,100和200个节点。节点之间存在四个维度的关系，即节点间存在着四种连接方式。同一社区间的节点以概率u进行连接，不属于同一社区的节点间的连接概率根据维度变化，即不同关系下的不同社区间节点的连接概率v不同。同时向网络中加入了噪声，噪声产生的方法是网络中所有节点之间以概率r进行随机连接。The multi-relational network used is an artificially generated network with a size of 350 nodes and three communities, each of which includes 50, 100 and 200 nodes. There are four-dimensional relationships between nodes, that is, there are four connection methods between nodes. Nodes in the same community are connected with probability u, and the connection probability between nodes that do not belong to the same community changes according to the dimension, that is, the connection probability v of nodes in different communities under different relationships is different. At the same time, noise is added to the network, and the noise is generated by random connection with probability r between all nodes in the network.
步骤二：将多关系网络的四个关系直接按照1:1比例来配置权重将多关系网络合并成一个带权重的单关系网络A，本发明实施例选用单关系的社区划分算法BGLL对网络A进行社区划分，所得的社区划分结果记为Ca，本发明实施例采用模块度作为衡量结果社区结构强度和可靠性的指标，计算结果Ca的模块度Qa，模块度计算如下：Step 2: directly configure the weights of the four relationships of the multi-relationship network according to the ratio of 1:1, and merge the multi-relationship networks into a weighted single-relationship network A. The embodiment of the present invention selects the single-relationship community division algorithm BGLL for network A Carry out community division, and the obtained community division result is denoted as Ca . In the embodiment of the present invention, modularity is used as an index to measure the strength and reliability of the community structure of the result, and the modularity Qa of the calculation result Ca is calculated as follows:
其中Ai，j是整个网络的邻接矩阵，m是网络中包含的边的数目，ki和kj分别表示节点i和节点j的度数，δ(Ci，Cj)的取值取决于i和j是否处于同一个社区内，是的话δ(Ci，Cj)取值为，否则话其取值为0。Among them, Ai, j is the adjacency matrix of the entire network, m is the number of edges contained in the network, ki and kj represent the degrees of node i and nodej respectively, and the value of δ(Ci , Cj ) depends on Whether i and j are in the same community, if yes, δ(Ci , Cj ) takes the value, otherwise it takes the value 0.
步骤三：以各关系的权重配比作为决策变量，采用一种多目标优化方法同时对下列两个子目标进行优化来获得一组最优决策变量集；Step 3: Take the weight ratio of each relationship as the decision variable, and use a multi-objective optimization method to optimize the following two sub-objectives at the same time to obtain a set of optimal decision variable sets;
优化子目标一：新的权重配比合并成的单关系网络B与网络A的社区划分结果的模块度差值尽可能大，优化子目标二：新的权重配比合并成的单关系网络B与网络A的社区划分结果所显示的社区结构信息相似性尽可能大，本实施案例使用标准化互信息NMI，按如下计算：Optimization sub-goal 1: The modularity difference between the community division results of the single-relationship network B combined with the new weight ratio and network A is as large as possible. Optimization sub-goal 2: The single-relationship network B combined with the new weight ratio The similarity with the community structure information displayed by the community division results of network A is as large as possible. In this implementation case, the standardized mutual information NMI is used and calculated as follows:
其中混淆矩阵H的行代表真实的社区划分结果，H的列代表划分算法画出来的社区结果。CA和CB分别代表A，B两个结果包含的社区个数，Hij代表应该在社区i中却出现在社区j中的节点个数，Hi.和H.j分别代表第i行和第j列的社区的节点数之和，N是整个网络中所含的节点数目。当NMI＝1时，代表A和B两个结果的社区结构完全相同，NMI＝0，时代表完全不一样。多目标遗传算法初始种群大小为50，交叉概率0.8，变异概率0.2，迭代次数300，编码方式为实数编码。The rows of the confusion matrix H represent the real community division results, and the columns of H represent the community results drawn by the division algorithm. CA and CB respectively represent the number of communities contained in the two results of A and B, Hij represents the number of nodes that should be in community i but appear in community j, Hi. and H.j represent row i respectively and the sum of the number of nodes in the community in column j, N is the number of nodes contained in the entire network. When NMI=1, the community structures representing the two results of A and B are completely the same, and when NMI=0, the representations are completely different. The initial population size of the multi-objective genetic algorithm is 50, the crossover probability is 0.8, the mutation probability is 0.2, the number of iterations is 300, and the encoding method is real number encoding.
步骤四：在步骤三获得的最优解集中选择使模块度值最大的解作为最终解，根据最终解给出的权重配比将多关系网络合并成单关系网络M，并采用一种单关系社区发现算法对M进行社区发现，将所获社区个数记为K，这里K＝3。Step 4: From the optimal solution set obtained in step 3, select the solution with the largest modularity value as the final solution, merge the multi-relational network into a single-relational network M according to the weight ratio given by the final solution, and adopt a single-relationship The community discovery algorithm performs community discovery on M, and records the number of communities obtained as K, where K=3.
步骤五：采用单关系社区发现算法BGLL分别对四个关系组成的网络进行社区划分，统计划分结果根据式子得到亲密度矩阵I，其中Iij为节点i,j在矩阵中对应的值，N为维度的总数这里是4,m表示第几个维度，Cm(i，j)表示两点在m维度是否被划分在同一社区，若两点在第m个维度被划为同一社区则Cm(i，j)值1，否则的话为0；遍历矩阵I，将所有值小于4的数全部设置为零，得到区域矩阵F；对矩阵F进行深度优先遍历，得到其所有的连通子区域，将子区域节点数目超过1的区域存入候选种子社区集合CL，L＝0。Step 5: Use the single-relationship community discovery algorithm BGLL to divide the community of the network composed of four relationships, and the statistical division results are according to the formula Get the intimacy matrix I, where Iij is the corresponding value of node i and j in the matrix, N is the total number of dimensions here is 4, m represents the dimension, Cm (i, j) represents two points in the m dimension Whether they are divided into the same community, if the two points are divided into the same community in the m-th dimension, the value of Cm (i, j) is 1, otherwise it is 0; traverse the matrix I, and set all the values less than 4 to Zero, get the area matrix F; perform depth-first traversal on the matrix F to get all its connected sub-areas, and store the areas with more than 1 sub-area nodes into the candidate seed community set CL , L=0.
步骤六：通过单关系网络M来计算网络中各节点之间的相似度Sim:Step 6: Calculate the similarity Sim between each node in the network through the single-relationship network M:
其中K表示i,j被划为相同社区的维度个数，N＝4，Δ增益因子为1，W(i，j)时节点i和节点j的连接边权重，com(i，j)两个节点邻居节点交集，N(i，j)是两个节点的邻居节点并集。Among them, K represents the number of dimensions that i and j are divided into the same community, N=4, Δ gain factor is 1, when W(i, j) is the connection edge weight of node i and node j, com(i, j) two N(i, j) is the union of neighbor nodes of two nodes.
步骤七：若L＝0，令L＝L+1，集合CL＝CL-1，进行下一步；否的话检测集合CL与CL-1是否一样，是的话转步骤十一，否则，令L＝L+1，集合CL＝CL-1进行下一步。Step 7: If L=0, set L=L+1, set CL =CL-1 , go to the next step; if not, check whether the set CL and CL-1 are the same, if yes, go to step eleven, otherwise , set L=L+1, and set CL =CL-1 to proceed to the next step.
步骤八：将种子社区候选集合CL中的尚未参与过合并的社区按照社区包含的节点个数多少排序，选取节点数最多的社区Si作为种子社区。Step 8: Sort the communities in the seed community candidate set CL that have not participated in the merger according to the number of nodes contained in the community, and select the community Si with the largest number of nodes as the seed community.
步骤九：计算种子社区Si与其余候选种子社区以及剩余节点的相似度，计算式子如下：Step 9: Calculate the similarity between the seed community Si and other candidate seed communities and remaining nodes, the calculation formula is as follows:
u和v分别是社区Si，Sj中的节点，ni和nj分别是两个社区中节点的数量，和是节点编号集合。u and v are the nodes in communities Si and Sj respectively, ni and nj are the numbers of nodes in the two communities respectively, with is a set of node numbers.
步骤十：选取与Si相似度超过设定阈值γ＝1的社区和节点放入候选区，计算Si当前适应度F以及候选区各社区的当前适应度Fh，计算公式如下：Step 10: Select communities and nodes whose similarity with Si exceeds the set threshold γ=1 and put them into the candidate area, calculate the current fitness F of Si and the current fitness Fh of each community in the candidate area, the calculation formula is as follows:
其中式子的是社区内部边的权重之和的两倍，是与社区外部边的权重之和，α为调控社区规模大小的参数，这里取值设为一；where the formula is twice the sum of the weights of the edges within the community, is the sum of the weights of the external edges of the community, α is a parameter to regulate the size of the community, and the value here is set to one;
然后分别计算候选合并区的社区和节点与Si合并后的适应度值记为，然后计算Fnew相对于Si原来的适应度F的增长率Vs以及候选社区适应度Fh的增长率Vh。Then calculate the fitness value of the community and node in the candidate merged area after merging with Si , and then calculate the growth rate Vs of Fnew relative to the original fitness F of Si and the growth rate of the candidate community fitness Fh Vh .
步骤十一：在Vs和Vh都大于增长率阈值δ＝0.1的前提下，选取Vs+Vh最大的那个社区与Si合并成一个新社区，更新Si和种子社区集合CL，返回步骤十；若没有符合条件的，则检查集合CL中现有社区是否都已是合并过的，否的话返回步骤九，是的话将集合CL中所有社区的合并记录清零，返回步骤八。Step 11: On the premise that both Vs and Vh are greater than the growth rate threshold δ=0.1, select the community with the largest Vs + Vh and merge it with Si to form a new community, and update Si and the seed community set CL , return to step 10; if there is no one that meets the conditions, check whether the existing communities in the set CL have been merged, if not, return to step 9, if yes, clear the merge records of all communities in the set CL , and return Step eight.
步骤十二：检查社区数目，若小于等与K，则输出结果，程序结束，输出集合CL；若大于K，则以包含节点数目最多的前K个社区为目标，依次计算剩余社区与他们的相似度，将剩余社区和节点归并入跟他们相似度最高的前K个社区，更新集合CL，最后输出社区集合CL作为最终划分结果。Step 12: Check the number of communities, if it is less than or equal to K, then output the result, the program ends, and output the set CL ; if it is greater than K, take the first K communities with the largest number of nodes as the target, and calculate the remaining communities and their Merge the remaining communities and nodes into the top K communities with the highest similarity with them, update the setCL , and finally output the community setCL as the final division result.
下面结合仿真对本发明的应用效果作详细的描述。The application effect of the present invention will be described in detail below in conjunction with simulation.
仿真一为本发明实施案例中u＝0.5，噪声r＝0.1的情况下本发明与只采用一种关系用BGLL算法进行社区发现的结果对比，采用NMI值来验证实验结果与真实社区结构的相似度，见图3。可以看出采用多种关系进行社区发现的结果优于只采用一种关系的结果。Simulation 1 is the case where u=0.5 and noise r=0.1 in the implementation case of the present invention. The comparison between the present invention and the results of community discovery using only one relationship using the BGLL algorithm, and the NMI value is used to verify that the experimental results are similar to the real community structure degree, see Figure 3. It can be seen that the results of using multiple relationships for community discovery are better than those using only one relationship.
仿真二为本发明实施案例中不断加大噪声时(从0.1增加到0.4，每次增加0.05)，本发明的检测结果与传统的PMM方法的对比，见图4。可以看出本发明的方法的抗噪音效果比较强。Simulation 2 is the comparison between the detection results of the present invention and the traditional PMM method when the noise is continuously increased in the implementation cases of the present invention (from 0.1 to 0.4, increasing by 0.05 each time), as shown in FIG. 4 . It can be seen that the anti-noise effect of the method of the present invention is relatively strong.
以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。The above descriptions are only preferred embodiments of the present invention, and are not intended to limit the present invention. Any modifications, equivalent replacements and improvements made within the spirit and principles of the present invention should be included in the protection of the present invention. within range.
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201710260510.6ACN107169871B (en) | 2017-04-20 | 2017-04-20 | A Multi-Relational Community Discovery Method Based on Relational Portfolio Optimization and Seed Dilation |
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201710260510.6ACN107169871B (en) | 2017-04-20 | 2017-04-20 | A Multi-Relational Community Discovery Method Based on Relational Portfolio Optimization and Seed Dilation |
| Publication Number | Publication Date |
|---|---|
| CN107169871Atrue CN107169871A (en) | 2017-09-15 |
| CN107169871B CN107169871B (en) | 2020-08-28 |
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201710260510.6AActiveCN107169871B (en) | 2017-04-20 | 2017-04-20 | A Multi-Relational Community Discovery Method Based on Relational Portfolio Optimization and Seed Dilation |
| Country | Link |
|---|---|
| CN (1) | CN107169871B (en) |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN106776781A (en)* | 2016-11-11 | 2017-05-31 | 深圳云天励飞技术有限公司 | A kind of human relation network analysis method and device |
| CN108648094A (en)* | 2018-05-08 | 2018-10-12 | 阿里巴巴集团控股有限公司 | A kind of community discovery method, device and equipment |
| CN108876116A (en)* | 2018-05-30 | 2018-11-23 | 西北工业大学 | A kind of creation effect knowledge recommendation method of Facing to Manufacturing technical optimization |
| CN112528166A (en)* | 2020-12-16 | 2021-03-19 | 平安养老保险股份有限公司 | User relationship analysis method and device, computer equipment and storage medium |
| CN113395172A (en)* | 2021-05-18 | 2021-09-14 | 中国电子科技集团公司第五十四研究所 | Important user discovery and behavior prediction method based on communication network |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102663499A (en)* | 2012-03-11 | 2012-09-12 | 西安电子科技大学 | Network community division method based on simulated annealing genetic algorithm |
| CN102768735A (en)* | 2012-07-04 | 2012-11-07 | 西安电子科技大学 | Network community division method based on immune cloning multi-objective optimization |
| CN104200272A (en)* | 2014-08-28 | 2014-12-10 | 北京工业大学 | Complex network community mining method based on improved genetic algorithm |
| CN104268629A (en)* | 2014-09-15 | 2015-01-07 | 西安电子科技大学 | Complex network community detecting method based on prior information and network inherent information |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102663499A (en)* | 2012-03-11 | 2012-09-12 | 西安电子科技大学 | Network community division method based on simulated annealing genetic algorithm |
| CN102768735A (en)* | 2012-07-04 | 2012-11-07 | 西安电子科技大学 | Network community division method based on immune cloning multi-objective optimization |
| CN104200272A (en)* | 2014-08-28 | 2014-12-10 | 北京工业大学 | Complex network community mining method based on improved genetic algorithm |
| CN104268629A (en)* | 2014-09-15 | 2015-01-07 | 西安电子科技大学 | Complex network community detecting method based on prior information and network inherent information |
| Title |
|---|
| 韩忠明 等: "NCSS: 一种快速有效的复杂网络社团划分算法", 《中国科学》* |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN106776781A (en)* | 2016-11-11 | 2017-05-31 | 深圳云天励飞技术有限公司 | A kind of human relation network analysis method and device |
| CN106776781B (en)* | 2016-11-11 | 2018-08-24 | 深圳云天励飞技术有限公司 | A kind of human relation network analysis method and device |
| CN108648094A (en)* | 2018-05-08 | 2018-10-12 | 阿里巴巴集团控股有限公司 | A kind of community discovery method, device and equipment |
| CN108876116A (en)* | 2018-05-30 | 2018-11-23 | 西北工业大学 | A kind of creation effect knowledge recommendation method of Facing to Manufacturing technical optimization |
| CN108876116B (en)* | 2018-05-30 | 2021-08-24 | 西北工业大学 | A Manufacturing Effect Knowledge Recommendation Method for Manufacturing Technology Optimization |
| CN112528166A (en)* | 2020-12-16 | 2021-03-19 | 平安养老保险股份有限公司 | User relationship analysis method and device, computer equipment and storage medium |
| CN113395172A (en)* | 2021-05-18 | 2021-09-14 | 中国电子科技集团公司第五十四研究所 | Important user discovery and behavior prediction method based on communication network |
| Publication number | Publication date |
|---|---|
| CN107169871B (en) | 2020-08-28 |
| Publication | Publication Date | Title |
|---|---|---|
| CN103678671B (en) | A kind of dynamic community detection method in social networks | |
| CN102929942B (en) | The overlapping community discovery method of a kind of community network based on integrated study | |
| CN107169871A (en) | It is a kind of to optimize many relation community discovery methods expanded with seed based on composition of relations | |
| CN111090780B (en) | Method and device for determining suspicious transaction information, storage medium and electronic equipment | |
| CN110705045B (en) | A link prediction method that uses network topology characteristics to construct weighted networks | |
| CN106452825A (en) | Power distribution and utilization communication network alarm correlation analysis method based on improved decision tree | |
| CN108090197A (en) | A kind of community discovery method of multidimensional social networks | |
| CN105956184A (en) | Method for identifying collaborative and organized junk information release team in micro-blog social network | |
| CN106533778A (en) | Method for identifying key node of command and control network based on hierarchical flow betweenness | |
| CN105608624A (en) | Microblog big data interest community analysis optimization method based on user experience | |
| CN110662232B (en) | Method for evaluating link quality by adopting multi-granularity cascade forest | |
| CN102664744A (en) | Group-sending recommendation method in network message communication | |
| CN107357858B (en) | A Location-Based Network Reconstruction Method | |
| CN109885797B (en) | A Relational Network Construction Method Based on Multi-Identity Space Mapping | |
| CN108287866A (en) | Community discovery method based on node density in a kind of large scale network | |
| CN113395172B (en) | Important user discovery and behavior prediction method based on communication network | |
| CN115775026A (en) | A Federated Learning Method Based on Organizational Similarity | |
| CN106952168A (en) | Attributed social network community division method based on multi-objective evolution | |
| CN103164533B (en) | Complex network community detection method based on information theory | |
| CN117520995B (en) | A method and system for abnormal user detection in network information platform | |
| CN106911512B (en) | Game-based link prediction method and system in commutative graphs | |
| CN112183820A (en) | Directed network link prediction method based on linear programming | |
| CN106296420A (en) | A kind of community discovery method | |
| Yuan et al. | A Multi‐Granularity Backbone Network Extraction Method Based on the Topology Potential | |
| CN115330056B (en) | A method for predicting users' influence on topic networks based on deep and broad propagation |
| 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 |