SimRank
સિમરેન્ક એ એક સામાન્ય સમાનતાનું માપ છે, જે એક સરળ અને સાહજિક આલેખ-સૈદ્ધાંતિક મોડેલ પર આધારિત છે. સિમરેન્ક ઑબ્જેક્ટ-ટુ-ઑબ્જેક્ટ સંબંધો સાથે કોઈપણ ડોમેનમાં લાગુ પડે છે, જે માળખાકીય સંદર્ભની સમાનતાને માપે છે જેમાં પદાર્થો અન્ય પદાર્થો સાથેના તેમના સંબંધોના આધારે થાય છે. અસરકારક રીતે, સિમરેન્ક એ એક માપ છે જે કહે છે કે "જો બે પદાર્થો સમાન પદાર્થો દ્વારા સંદર્ભિત હોય તો તેમને સમાન ગણવામાં આવે છે". સિમરેન્ક વ્યાપકપણે અપનાવવામાં આવ્યું હોવા છતાં, તે ગેરવાજબી સમાનતા સ્કોર્સ ઉત્પન્ન કરી શકે છે જે વિવિધ પરિબળોથી પ્રભાવિત હોય છે, અને તેને ઘણી રીતે ઉકેલી શકાય છે, જેમ કે પુરાવા વજન પરિબળ રજૂ કરવું, સિમરેન્ક દ્વારા અવગણવામાં આવેલા વધારાના શબ્દો દાખલ કરવા અથવા પેજરેન્ક-આધારિત વિકલ્પોનો ઉપયોગ કરવો. પરિચય ઘણી એપ્લિકેશનો માટે પદાર્થો વચ્ચે "સમાનતા" નું માપ જરૂરી છે. એક સ્પષ્ટ ઉદાહરણ પરંપરાગત ટેક્સ્ટ કોર્પોરા અથવા વર્લ્ડ વાઇડ વેબ પર "શોધ-સમાન-દસ્તાવેજ" ક્વેરી છે. વધુ સામાન્ય રીતે, સમાનતાના માપનો ઉપયોગ વસ્તુઓને ક્લસ્ટર કરવા માટે થઈ શકે છે, જેમ કે ભલામણ પ્રણાલીમાં સહયોગી ગાળણ માટે, જેમાં "સમાન" વપરાશકર્તાઓ અને વસ્તુઓને વપરાશકર્તાઓની પસંદગીઓના આધારે જૂથબદ્ધ કરવામાં આવે છે. વસ્તુઓના વિવિધ પાસાઓનો ઉપયોગ સમાનતા નક્કી કરવા માટે થઈ શકે છે, જે સામાન્ય રીતે ડોમેન અને તે ડોમેન માટે સમાનતાની યોગ્ય વ્યાખ્યાના આધારે હોય છે. દસ્તાવેજના કોષમાં, મેળ ખાતા લખાણનો ઉપયોગ કરી શકાય છે, અને સહયોગી ગાળણ માટે, સમાન વપરાશકર્તાઓને સામાન્ય પસંદગીઓ દ્વારા ઓળખી શકાય છે. સિમરેન્ક એ એક સામાન્ય અભિગમ છે જે રસના ઘણા ક્ષેત્રોમાં જોવા મળતા ઓબ્જેક્ટ-ટુ-ઓબ્જેક્ટ સંબંધોનો ઉપયોગ કરે છે. વેબ પર, ઉદાહરણ તરીકે, જો તેમની વચ્ચે હાયપરલિંક્સ હોય તો બે પૃષ્ઠો સંબંધિત છે. સમાન અભિગમ વૈજ્ઞાનિક કાગળો અને તેમના ટાંકણો, અથવા ક્રોસ-રેફરન્સ માહિતી સાથે અન્ય કોઈપણ દસ્તાવેજ કોર્પસને લાગુ કરી શકાય છે. ભલામણ પ્રણાલીઓના કિસ્સામાં, વસ્તુ માટે વપરાશકર્તાની પસંદગી વપરાશકર્તા અને વસ્તુ વચ્ચેના સંબંધની રચના કરે છે. આવા ડોમેન્સ કુદરતી રીતે આલેખ તરીકે તૈયાર કરવામાં આવે છે, જેમાં પદાર્થોનું પ્રતિનિધિત્વ કરતા નોડ્સ અને સંબંધોનું પ્રતિનિધિત્વ કરતી ધાર હોય છે. સિમરેન્ક અલ્ગોરિધમ પાછળનો અંતઃપ્રેરણા એ છે કે, ઘણા ક્ષેત્રોમાં, સમાન પદાર્થોને સમાન પદાર્થો દ્વારા સંદર્ભિત કરવામાં આવે છે. વધુ ચોક્કસપણે, પદાર્થો અને સમાન ગણવામાં આવે છે જો તેઓ પદાર્થોથી અનુક્રમે નિર્દેશ કરે છે અને અને પોતાને સમાન હોય છે. બેઝ કેસ એ છે કે પદાર્થો મહત્તમ પોતાને સમાન હોય છે. એ નોંધવું અગત્યનું છે કે સિમરેન્ક એ એક સામાન્ય અલ્ગોરિધમ છે જે ફક્ત માળખાકીય સંદર્ભની સમાનતા નક્કી કરે છે. સિમરેન્ક કોઈપણ ડોમેનને લાગુ પડે છે જ્યાં સંબંધો પર સમાનતાની ઓછામાં ઓછી કેટલીક કલ્પનાને આધાર આપવા માટે પદાર્થો વચ્ચે પૂરતા સુસંગત સંબંધો હોય છે. દેખીતી રીતે, અન્ય ક્ષેત્ર-વિશિષ્ટ પાસાઓની સમાનતા પણ મહત્વપૂર્ણ છે; આ કરી શકાય છે-અને એકંદર સમાનતા માપ માટે સંબંધિત માળખાકીય-સંદર્ભ સમાનતા સાથે જોડવી જોઈએ. ઉદાહરણ તરીકે, વેબ પૃષ્ઠો માટે સિમરેન્કને પરંપરાગત લખાણની સમાનતા સાથે જોડી શકાય છે; આ જ વિચાર વૈજ્ઞાનિક કાગળો અથવા અન્ય દસ્તાવેજ સમૂહને લાગુ પડે છે. ભલામણ પ્રણાલીઓ માટે, વસ્તુઓ વચ્ચે બિલ્ટ-ઇન જાણીતી સમાનતાઓ હોઈ શકે છે (દા. ત., બંને કમ્પ્યુટર, બંને કપડાં, વગેરે). ), તેમજ વપરાશકર્તાઓ વચ્ચે સમાનતા (દા. ત., સમાન લિંગ, સમાન ખર્ચ સ્તર). ફરીથી, આ સમાનતાઓને સમાનતા સ્કોર્સ સાથે જોડી શકાય છે, જે એકંદર સમાનતા માપ પેદા કરવા માટે પસંદગીની પેટર્નના આધારે ગણવામાં આવે છે. મૂળભૂત સિમરેન્ક સમીકરણ નિર્દેશિત આલેખમાં નોડ માટે, આપણે અનુક્રમે પડોશીઓ અને બહારના પડોશીઓના સમૂહ દ્વારા સૂચવીએ છીએ. વ્યક્તિગત પડોશીઓને માટે તરીકે સૂચવવામાં આવે છે અને વ્યક્તિગત બહારના પડોશીઓને માટે તરીકે સૂચવવામાં આવે છે. ચાલો આપણે પદાર્થો અને દ્વારા વચ્ચેની સમાનતા દર્શાવીએ. અગાઉના પ્રેરણાને અનુસરીને, પુનરાવર્તિત સમીકરણ માટે લખવામાં આવે છે. જો પછી વ્યાખ્યાયિત કરવામાં આવે છે. નહિંતર, જ્યાં અને વચ્ચે અચળાંક છે. અહીં થોડી તકનિકીતા એ છે કે તેમાં કોઈ પડોશીઓ હોઈ શકે છે અથવા ન પણ હોઈ શકે. આ કિસ્સામાં અને વચ્ચે કોઈ સમાનતા અનુમાન કરવાની કોઈ રીત નથી, તેથી સમાનતા સેટ કરવામાં આવે છે, તેથી ઉપરોક્ત સમીકરણમાં સરવાળાને ક્યારે અથવા તરીકે વ્યાખ્યાયિત કરવામાં આવે છે. સિમરેન્કની મેટ્રિક્સ રજૂઆત અને વચ્ચે મનસ્વી અચળાંક આપવામાં આવે તો, ચાલો સમાનતા મેટ્રિક્સ હોઈએ જેની એન્ટ્રી સમાનતા સ્કોરને સૂચવે છે, અને કૉલમ નોર્મલાઇઝ્ડ અડ્જસેન્સી મેટ્રિક્સ હોઈ શકે છે જેની એન્ટ્રી જો ત્યાં કોઈ ધાર હોય તો, અને અન્યથા 0. પછી, મેટ્રિક્સ સંકેતોમાં, સિમરેન્કને ઓળખ મેટ્રિક્સ તરીકે તૈયાર કરી શકાય છે. સિમરેન્કની ગણતરી ગ્રાફ માટે સિમરેન્ક સમીકરણોના ઉકેલ સુધી નિશ્ચિત બિંદુ પર પુનરાવર્તન દ્વારા પહોંચી શકાય છે. ચાલો તેમાં ગાંઠોની સંખ્યા હોઈએ. દરેક પુનરાવર્તન માટે, આપણે એન્ટ્રીઓ રાખી શકીએ છીએ, જ્યાં વચ્ચે અને પુનરાવર્તન પર સ્કોર આપે છે. આપણે તેના આધારે ક્રમિક રીતે ગણતરી કરીએ છીએ. આપણે વાસ્તવિક સિમરેન્ક સ્કોર પર જ્યાં દરેક નીચી સીમા છે ત્યાંથી શરૂઆત કરીએ છીએઃ તેમાંથી ગણતરી કરવા માટે, આપણે મૂળભૂત સિમરેન્ક સમીકરણનો ઉપયોગ મેળવવા માટે કરીએ છીએઃ માટે, અને માટે. એટલે કે, દરેક પુનરાવર્તન પર, આપણે મૂળભૂત સિમરેન્ક સમીકરણ અનુસાર અગાઉના પુનરાવર્તનના પડોશીઓના સમાનતા સ્કોર્સનો ઉપયોગ કરવાની સમાનતાને અપડેટ કરીએ છીએ. જેમ જેમ વધારો થાય છે તેમ તેમ મૂલ્યો ઘટતા નથી. તે દર્શાવવામાં આવ્યું હતું કે મૂલ્યો મૂળભૂત સિમરેન્ક સમીકરણ, સિમરેન્ક સ્કોર્સ, એટલે કે, બધા માટે, સંતોષકારક મર્યાદાઓમાં ભેગા થાય છે. મૂળ સિમરેન્ક દરખાસ્તમાં પ્રદર્શન કરવા માટે ક્ષય પરિબળ અને નિશ્ચિત સંખ્યામાં પુનરાવર્તનો પસંદ કરવાનું સૂચન કરવામાં આવ્યું હતું. જો કે, તાજેતરના સંશોધનોએ દર્શાવ્યું છે કે આપેલ મૂલ્યો અને સામાન્ય રીતે પુનરાવર્તિત રીતે ગણતરી કરાયેલા સિમરેન્ક સ્કોર્સની પ્રમાણમાં ઓછી ચોકસાઈ સૂચવે છે. વધુ સચોટ ગણતરી પરિણામોની બાંયધરી આપવા માટે, પછીનું પેપર સૂચવે છે કે કાં તો નાના ક્ષય પરિબળ (ખાસ કરીને) નો ઉપયોગ કરવો અથવા વધુ પુનરાવર્તનો લેવા. કોસિમરેન્ક કોસિમરેન્ક એ સિમરેન્કનો એક પ્રકાર છે, જેમાં સ્થાનિક ફોર્મ્યુલેશનનો પણ ફાયદો છે, એટલે કે. કોસિમરેન્કની ગણતરી એક જ નોડ જોડી માટે કરી શકાય છે. ચાલો સમાનતા મેટ્રિક્સ હોઈએ જેની એન્ટ્રી સમાનતા સ્કોરને સૂચવે છે, અને સ્તંભ સામાન્યીકૃત સંલગ્નતા મેટ્રિક્સ હોઈ શકે છે. પછી, મેટ્રિક્સ સંકેતોમાં, કોસિમરેન્કને આ રીતે ઘડી શકાય છેઃ ઓળખ મેટ્રિક્સ ક્યાં છે. માત્ર એક જ નોડ જોડીના સમાનતા સ્કોરની ગણતરી કરવા માટે, ચાલો, પ્રમાણભૂત આધારના વેક્ટર હોવા સાથે, એટલે કે,-th એન્ટ્રી 1 છે અને અન્ય તમામ એન્ટ્રીઓ 0 છે. પછી, કોસિમરેન્કની ગણતરી બે તબક્કામાં કરી શકાય છેઃ પ્રથમ પગલું વ્યક્તિગત પેજરેન્કનું સરળીકૃત સંસ્કરણ જોઈ શકાય છે. પગલું બે દરેક પુનરાવર્તનની વેક્ટર સમાનતાનો સારાંશ આપે છે. મેટ્રિક્સ અને સ્થાનિક પ્રતિનિધિત્વ બંને, સમાન સમાનતા સ્કોરની ગણતરી કરે છે. કોસિમરેન્કનો ઉપયોગ નોડ્સના સમૂહોની સમાનતાની ગણતરી કરવા માટે પણ થઈ શકે છે. સિમરેન્ક ફોગારસ અને રેઝ પરના વધુ સંશોધનોએ મોન્ટે કાર્લો પદ્ધતિનો ઉપયોગ કરીને સંભવિત ગણતરી દ્વારા સિમરેન્કની ગણતરીને ઝડપી બનાવવાનું સૂચન કર્યું. એન્ટોનેલિસ એટ અલ. વિસ્તૃત સિમરેન્ક સમીકરણોને ધ્યાનમાં લેવા માટે (i) ઇન્સિડેન્ટ નોડ્સ માટે પુરાવા પરિબળ અને (ii) લિંક વજન. યુ એટ અલ. નાના સામાન્ય ભાગોને વિવિધ આંશિક રકમોમાં વહેંચવા માટે ફાઇન-ગ્રેઇન મેમોઇઝેશન પદ્ધતિ દ્વારા સિમરેન્કની ગણતરીમાં વધુ સુધારો થયો. ચેન અને જાઇલ્સે સિમરેન્કની મર્યાદાઓ અને યોગ્ય ઉપયોગના કિસ્સાઓની ચર્ચા કરી હતી. આંશિક સમ મેમોઇઝેશન લિઝોર્કિન એટ અલ. સિમરેન્કની ગણતરીને ઝડપી બનાવવા માટે પ્રસ્તાવિત ત્રણ ઓપ્ટિમાઇઝેશન તકનીકોઃ આવશ્યક નોડ્સની પસંદગી એ-પ્રાયોરી શૂન્ય સ્કોર્સ સાથે નોડ જોડીઓના અપૂર્ણાંકની ગણતરીને દૂર કરી શકે છે. આંશિક રકમ યાદગીરી પછીના પુનઃઉપયોગ માટે સમાનતાના સરવાળાના ભાગને કેશ કરીને વિવિધ નોડ જોડીઓ વચ્ચેની સમાનતાની પુનરાવર્તિત ગણતરીઓને અસરકારક રીતે ઘટાડી શકે છે. સમાનતા પર થ્રેશોલ્ડ સેટિંગ ગણતરી કરવા માટે નોડ જોડીઓની સંખ્યામાં વધુ ઘટાડાને સક્ષમ કરે છે. ખાસ કરીને, આંશિક સમ મેમોઇઝેશનનું બીજું અવલોકન સિમરેન્કની ગણતરીને મોટા પ્રમાણમાં ઝડપી બનાવવામાં સર્વોચ્ચ ભૂમિકા ભજવે છે, જ્યાં પુનરાવર્તનોની સંખ્યા છે, ગ્રાફની સરેરાશ ડિગ્રી છે, અને ગ્રાફમાં ગાંઠોની સંખ્યા છે. આંશિક સમ મેમોઇઝેશનના કેન્દ્રિય વિચારમાં બે પગલાંઓનો સમાવેશ થાય છેઃ પ્રથમ, આંશિક રકમને મેમોઇઝ કરવામાં આવે છે અને પછી પુનરાવર્તિત રીતે તેની ગણતરી કરવામાં આવે છે પરિણામે, જ્યારે આપણે પ્રથમ દલીલ તરીકે આપેલ શિરોબિંદુ માટેની સમાનતાની ગણતરી કરીએ ત્યારે, ના પરિણામોનો પછીથી ફરીથી ઉપયોગ કરી શકાય છે. પેજરેન્ક સાઇટેશન સોર્સ ક્લસ્ટર એનાલિસિસ એલ્ગોરિધમ્સ પણ જુઓ સમાનતા પગલાં